Cet article est, dans une certaine mesure, une continuation de mon article sur la minimisation des fonctions logiques par la méthode Quine-Mac'Klaski (
https://habr.com/post/328506 ). Il a considéré un cas avec des fonctions logiques complètement définies (bien que cela n'y soit pas directement mentionné, mais seulement implicite). En réalité, un tel cas est assez rare lorsque le nombre de variables d'entrée est petit. Les fonctions logiques dont la définition est partielle ou incomplète ne sont données que pour la partie Q de l'ensemble complet P =
ensembles (termes) possibles de leurs arguments (variables) de nombre
N , c'est-à-dire Q <P. Cette situation se rencontre en pratique dans la plupart des cas d'application d'algorithmes d'optimisation de fonctions logiques. En effet, par exemple, si le nombre de variables d'entrée est
N = 30, ce qui est un cas ordinaire, par exemple, sur les marchés financiers, alors le volume de l'échantillon de formation d'entrée devrait être de l'ordre de
>
termes uniques uniques. Un tel ensemble de données ne se retrouve pas dans toutes les organisations, même très grandes, sans parler des individus, c'est-à-dire que c'est déjà le domaine du BigData, de l'utilisation des centres de données, etc.
Par conséquent, dans la pratique, le plus souvent, les fonctions logiques minimisées ne seront pas complètement déterminées simplement en raison du manque de quantité requise de données accumulées ou pour diverses autres raisons objectives (par exemple, il n'y a pas assez d'espace pour les stocker). La question se pose de la possibilité de «contournement» de ce problème lors de l'utilisation d'un algorithme qui fonctionne avec un ensemble complètement défini de fonctions de logique thermique, comme, par exemple, dans mon article précédent.
Dans ce cas, la pratique standard consiste à déterminer l'ensemble d'entrée incomplet de valeurs de variable (terme) à l'ensemble afin de donner un résultat optimal pour l'ensemble de données existant. Mais, dans ce cas, il y a un problème à énumérer toutes les variantes possibles de définitions supplémentaires, dont le nombre total est V =
pour sélectionner la meilleure option pour une définition supplémentaire en fonction d'un critère donné. De toute évidence, pour les valeurs réellement utilisées de Q et P, le nombre d'options triées pour des définitions supplémentaires est astronomiquement important et cette approche ne peut pas être mise en œuvre dans la pratique en raison de l'immense coût de calcul.
Ainsi, une approche différente est nécessaire qui éliminerait la nécessité d'énumérer diverses options pour des définitions supplémentaires. Par conséquent, il est nécessaire de moderniser l'algorithme d'origine, qui ne fonctionne initialement qu'avec un ensemble d'entrée entièrement défini, afin qu'il puisse également fonctionner avec un ensemble tronqué. C'est une telle implémentation de l'algorithme qui est proposée dans cet article, basée sur le fait que pendant le processus de minimisation, deux listes incomplètes de termes sont traitées simultanément, sur lesquelles la fonction est spécifiée comme FAUX (0) et VRAI (1).
Du point de vue de l'apprentissage automatique, l'algorithme Quine-Mac'Klaski met en œuvre le paradigme d'apprentissage avec l'enseignant lorsque les valeurs de sortie correspondantes de la fonction objectif sont impliquées dans le processus d'apprentissage (dans ce cas, la minimisation) simultanément. Permettez-moi de vous rappeler que le principe de fonctionnement de la méthode de base Quine-Mac'Klaski selon la théorie se compose de deux étapes principales:
- Stage. Trouver tous les termes LF simples en utilisant des règles de collage (lois):
a) (A et B)? (A et! B)? A;
b) (A? B) & (A?! B)? A;
où & est l'opération logique ET;? - fonctionnement du "OU" logique;! - opération de négation logique "NON". De ces formules, il s'ensuit que deux termes sont collés ensemble s'ils ne diffèrent l'un de l'autre que dans l'une des positions des variables. Dans la position où les deux termes diffèrent l'un de l'autre, le signe «*» est placé. Ainsi, l'alphabet en termes collés par rapport à l'original se développe en trois valeurs:
• 0 => faux;
• 1 => vrai;
• 2 => variable collée (*). - Stage. Minimisation du nombre de termes collés obtenus après la première étape, comme problème de trouver la couverture optimale de l'ensemble initial de termes avec la quantité Q. Autrement dit, puisque chaque terme de sortie ne couvre qu'un certain sous-ensemble des termes initiaux, il est nécessaire de choisir un ensemble minimal de termes de sortie qui sont identifiés avec avec eux, des sous-ensembles de différentes longueurs au total couvraient complètement tous les termes d'entrée initiaux. Le revêtement dans ce cas signifie que l'opération au niveau du bit de disjonction du terme de sortie sur le terme d'entrée a donné une vraie valeur. Disons que le terme de sortie collé a la forme suivante: 10 * 0110 *.
Ensuite, il couvre le terme 10101100:
10 * 0110 * & 10101100 = VRAI
mais ne couvre pas le terme 00101100:
10 * 0110 * & 00101100 = FAUX
Autrement dit, le terme d'entrée et la sortie doivent coïncider partout sauf pour les positions où il y a un symbole «*» - à cette position, la variable du terme d'entrée peut prendre n'importe quelle valeur, car dans cette position, la variable est exclue de la considération.
Le code d'implémentation est le suivant (cliquez pour voir):using System; using System.Collections.Generic; using System.Linq; #region /// <summary> /// /// </summary> public abstract class LogicFunction { // "" public const byte cStarSymb = 2; // public readonly ICollection<byte[]> Terms = new LinkedList<byte[]>(); // public abstract bool Calculate(bool[] X); // public abstract bool Calculate(char[] X); // public abstract bool Calculate(byte[] X); } /// <summary> /// /// </summary> public class Dnf : LogicFunction { public static bool Calculate(byte[] X, byte[] term) { bool bResult = true; for (int i = 0; i < term.Length; i++) { if ((term[i] == cStarSymb) || (term[i] == X[i])) continue; bResult = false; break; } return bResult; } public override bool Calculate(byte[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || (term[i] == X[i])) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } public override bool Calculate(char[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || (term[i] == (byte)(X[i] == '0' ? 0 : 1))) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } public override bool Calculate(bool[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || ((term[i] != 0) == X[i])) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } } #endregion /// <summary> /// /// </summary> public class TreeFuncTerm { /// <summary> /// /// </summary> public class TreeNodeEnd { } // private readonly TreeNodeEnd pCommonTreeNodeEnd = new TreeNodeEnd(); // private readonly object[] rootNode = new object[3]; // () private int _rang = 0; public int Rang { get { return _rang; } } // private int enumerationPos = 0; private object[][] enumerationBuf; //, private byte[] enumerationTerm; public byte[] EnumerationTerm { get { return enumerationTerm; } } // private UInt32 _count = 0; public UInt32 Count { get { return _count; } } // public TreeFuncTerm() { Clear(); } // public void Clear() { _count = 0; _rang = 0; enumerationPos = 0; enumerationBuf = null; enumerationTerm = null; rootNode[0] = rootNode[1] = rootNode[2] = null; } // public TreeNodeEnd EnumerationInit() { enumerationPos = 0; enumerationTerm = new byte[_rang]; enumerationTerm[0] = 0; enumerationBuf = new object[_rang][]; enumerationBuf[0] = rootNode; // return EnumerationNextNode(); } // public TreeNodeEnd EnumerationNextNode() { int iIsNext = (enumerationPos > 0 ? 1 : 0); TreeNodeEnd pRetTreeNode = null; while ((pRetTreeNode == null) && (enumerationPos >= 0)) { object[] pCurrNodes = enumerationBuf[enumerationPos]; object pNextNode = null; int i = enumerationTerm[enumerationPos] + iIsNext; for (; i < 3; i++) if ((pNextNode = pCurrNodes[i]) != null) break; if (pNextNode == null) { // enumerationPos--; iIsNext = 1; } else { enumerationTerm[enumerationPos] = (byte)i; if (pNextNode is object[]) { // enumerationPos++; enumerationBuf[enumerationPos] = (object[])pNextNode; enumerationTerm[enumerationPos] = 0; iIsNext = 0; } else //if (pNextNode is TreeNodeEnd) { // pRetTreeNode = (TreeNodeEnd)pNextNode; } } } return pRetTreeNode; } // public void AddTerm(byte[] term) { _rang = Math.Max(_rang, term.Length); object[] pCurrNode = rootNode; int iTermLength1 = term.Length - 1; for (int j = 0; j < iTermLength1; j++) { byte cSymb = term[j]; object item = pCurrNode[cSymb]; if (item == null) { item = new object[3]; pCurrNode[cSymb] = item; } pCurrNode = (object[])item; } if (pCurrNode[term[iTermLength1]] == null) { // pCurrNode[term[iTermLength1]] = pCommonTreeNodeEnd; _count++; } } // public TreeNodeEnd Remove(byte[] term) { int iTermLength1 = term.Length - 1; object[] pCurrNode = rootNode; for (int i = 0; i < iTermLength1; i++) { pCurrNode = (object[])pCurrNode[term[i]]; if (pCurrNode == null) break; } TreeNodeEnd pRemovedNode = null; if (pCurrNode != null) { // pRemovedNode = (TreeNodeEnd)pCurrNode[term[iTermLength1]]; if (pRemovedNode != null) { // pCurrNode[term[iTermLength1]] = null; // - _count--; } } return pRemovedNode; } // public bool Contains(byte[] term) { object pCurrNode = rootNode; foreach (byte cSymb in term) { pCurrNode = ((object[])pCurrNode)[cSymb]; if (pCurrNode == null) break; } return ((pCurrNode != null) && (pCurrNode is TreeNodeEnd)); } } /// <summary> /// ---- /// </summary> public class Quine_McCluskey { // private readonly Dnf _result = new Dnf(); public Dnf Result { get { return _result; } } // private readonly Dnf _resultNeg = new Dnf(); public Dnf ResultNeg { get { return _resultNeg; } } // private static void Skleivanie(TreeFuncTerm X1Tree, TreeFuncTerm X2Tree, TreeFuncTerm NegativTree, IEnumerable<byte[]> InpNegTerms, Dictionary<int, LinkedList<byte[]>> OutResult, int iLevel) { LinkedList<byte[]> OutR = new LinkedList<byte[]>(); if (OutResult != null) OutResult.Add(iLevel, OutR); bool IsVirtSkleivOn = ((NegativTree != null) && (InpNegTerms != null) && (InpNegTerms.Count() != 0)); for (TreeFuncTerm.TreeNodeEnd x1 = X1Tree.EnumerationInit(); x1 != null; x1 = X1Tree.EnumerationNextNode()) { bool bIsSkleiv = false; byte[] pCurrTerm = X1Tree.EnumerationTerm; for (int iPos = 0; iPos < pCurrTerm.Length; iPos++) { byte cSymbSav = pCurrTerm[iPos]; if (cSymbSav == LogicFunction.cStarSymb) continue; // pCurrTerm[iPos] = (byte)(1 - cSymbSav); if (X1Tree.Contains(pCurrTerm)) { bIsSkleiv = true; //, if (cSymbSav == 1) { pCurrTerm[iPos] = LogicFunction.cStarSymb; // X2Tree.AddTerm(pCurrTerm); } } // , NegativTree else if (IsVirtSkleivOn && !NegativTree.Contains(pCurrTerm)) { bool bIsNotCanAdd = false; pCurrTerm[iPos] = LogicFunction.cStarSymb; // foreach (byte[] NegTerm in InpNegTerms) { if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break; } if (!bIsNotCanAdd) { bIsSkleiv = true; X2Tree.AddTerm(pCurrTerm); } } pCurrTerm[iPos] = cSymbSav; } // , if (!bIsSkleiv) OutR.AddLast((byte[])pCurrTerm.Clone()); } } // private static UInt64 GetTermCode(byte[] pTerm) { UInt64 iMultip = 1, iCode = 0; for (int i = 0; i < pTerm.Length; i++) { iCode += (iMultip * pTerm[i]); iMultip *= 3; } return iCode; } // private static byte[] GetTermByCode(UInt64 iCode, int iTermLength, byte[] pTerm = null) { if (pTerm == null) pTerm = new byte[iTermLength]; int iCounter = 0; while (iCode != 0) { pTerm[iCounter++] = (byte)(iCode % 3); iCode /= 3; } while (iCounter < iTermLength) pTerm[iCounter++] = 0; return pTerm; } // private static void Skleivanie(ICollection<UInt64> X1Tree, ICollection<UInt64> X2Tree, ICollection<UInt64> NegativTree, IEnumerable<byte[]> InpNegTerms, Dictionary<int, LinkedList<byte[]>> OutResult, int iLevel, int iTermLength) { LinkedList<byte[]> OutR = new LinkedList<byte[]>(); if (OutResult != null) OutResult.Add(iLevel, OutR); byte[] pCurrTerm = new byte[iTermLength]; bool IsVirtSkleivOn = ((NegativTree != null) && (InpNegTerms != null) && (InpNegTerms.Count() != 0)); foreach (UInt64 x1 in X1Tree) { GetTermByCode(x1, iTermLength, pCurrTerm); bool bIsSkleiv = false; UInt64 iMultip = 1; for (int iPos = 0; iPos < iTermLength; iPos++) { byte cSymbSav = pCurrTerm[iPos]; //(byte)((x1 / iMultip) % 3); if (cSymbSav != LogicFunction.cStarSymb) { UInt64 iCode = (cSymbSav == 0 ? x1 + iMultip : x1 - iMultip); // if (X1Tree.Contains(iCode)) { bIsSkleiv = true; //, if (cSymbSav == 1) { X2Tree.Add(x1 + iMultip); } } // , NegativTree else if (IsVirtSkleivOn && !NegativTree.Contains(iCode)) { bool bIsNotCanAdd = false; pCurrTerm[iPos] = LogicFunction.cStarSymb; // foreach (byte[] NegTerm in InpNegTerms) { if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break; } pCurrTerm[iPos] = cSymbSav; if (!bIsNotCanAdd) { bIsSkleiv = true; X2Tree.Add(x1 + (byte)(LogicFunction.cStarSymb - cSymbSav) * iMultip); } } } iMultip *= 3; } // , if (!bIsSkleiv) OutR.AddLast((byte[])pCurrTerm.Clone()); } } // // private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, ICollection<UInt64> OutX2Tree) { OutX2Tree.Clear(); foreach (byte[] x1 in InX1) { UInt64 iCode = GetTermCode(x1); if (OutX2Tree.Contains(iCode)) continue; OutX2Tree.Add(iCode); } } // // private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, TreeFuncTerm OutX2Tree) { OutX2Tree.Clear(); foreach (byte[] x1 in InX1) OutX2Tree.AddTerm(x1); } // private static bool IsEqualTerms(byte[] pTermC, byte[] pTermB) { if ((pTermC == null) || (pTermB == null) || (pTermC.Length != pTermB.Length)) return false; bool bIsEqual = false; int iLength = Math.Min(pTermC.Length, pTermB.Length); for ( int i = 0; i < iLength; i++) { if (!(bIsEqual = (pTermB[i] == pTermC[i]))) break; } return bIsEqual; } // private static void ReduceRedundancyTerms(LinkedList<byte[]> InpTerms, Dictionary<int, LinkedList<byte[]>> SkleivTerms, ICollection<byte[]> ResultTerms) { if ((InpTerms == null) || (SkleivTerms == null) || (ResultTerms == null)) return; // ResultTerms.Clear(); // , Dictionary<byte[], HashSet<byte[]>> Outputs2Inputs = new Dictionary<byte[], HashSet<byte[]>>(); // , Dictionary<byte[], HashSet<byte[]>> Inputs2Outputs = new Dictionary<byte[], HashSet<byte[]>>(); // foreach (int iLevel in SkleivTerms.Keys.OrderByDescending(p => p).AsEnumerable()) { // foreach (byte[] outTerm in SkleivTerms[iLevel]) { // , term HashSet<byte[]> InpTermsLst = new HashSet<byte[]>(); // foreach (byte[] inpTerm in InpTerms) { if (Dnf.Calculate(inpTerm, outTerm)) { InpTermsLst.Add(inpTerm); if (!Inputs2Outputs.ContainsKey(inpTerm)) Inputs2Outputs.Add(inpTerm, new HashSet<byte[]>()); Inputs2Outputs[inpTerm].Add(outTerm); } } Outputs2Inputs.Add(outTerm, InpTermsLst); } } // - Inputs2Outputs = Inputs2Outputs.OrderBy(p => p.Value.Count).ToDictionary(p => p.Key, v => v.Value); // , - while (Inputs2Outputs.Count > 0) { byte[] outTerm = Inputs2Outputs.First().Value.OrderByDescending(q => Outputs2Inputs[q].Count()).First(); ResultTerms.Add(outTerm); foreach (byte[] inpTerm in Outputs2Inputs[outTerm].ToArray()) { foreach (byte[] outTerm2Del in Inputs2Outputs[inpTerm]) Outputs2Inputs[outTerm2Del].Remove(inpTerm); Inputs2Outputs.Remove(inpTerm); } } } // public static void LogicFuncMinimize(IEnumerable<byte[]> PositivTerms, ICollection<byte[]> OutPos, IEnumerable<byte[]> NegativTerms, ICollection<byte[]> OutNeg) { int iTotalLevels = (PositivTerms.Count() > 0 ? PositivTerms.First().Length : (NegativTerms != null && NegativTerms.Count() > 0 ? NegativTerms.First().Length : 0)); Dictionary<int, LinkedList<byte[]>> SkleivPosTerms = new Dictionary<int, LinkedList<byte[]>>(iTotalLevels); Dictionary<int, LinkedList<byte[]>> SkleivNegTerms = new Dictionary<int, LinkedList<byte[]>>(iTotalLevels); LinkedList<byte[]> InpPosTerms = new LinkedList<byte[]>(); LinkedList<byte[]> InpNegTerms = new LinkedList<byte[]>(); if (iTotalLevels < 40) { HashSet<UInt64> X1PositivTree = new HashSet<UInt64>(); DeleteDublicatingTerms(PositivTerms, X1PositivTree); HashSet<UInt64> X1NegativTree = null; if (NegativTerms != null) { X1NegativTree = new HashSet<UInt64>(); DeleteDublicatingTerms(NegativTerms, X1NegativTree); // foreach(UInt64 iNumb in X1PositivTree.Intersect(X1NegativTree)) { // - X1 NegativTerms int iPos_Count = PositivTerms.Count(p => GetTermCode(p) == iNumb); int iNeg_Count = NegativTerms.Count(p => GetTermCode(p) == iNumb); if (iPos_Count > iNeg_Count) { X1NegativTree.Remove(iNumb); } else if (iPos_Count < iNeg_Count) { X1PositivTree.Remove(iNumb); } else //if (iPos_Count == iNeg_Count) { X1PositivTree.Remove(iNumb); X1NegativTree.Remove(iNumb); } } // foreach (UInt64 code in X1NegativTree) { InpNegTerms.AddLast(GetTermByCode(code, iTotalLevels)); } } // foreach (UInt64 code in X1PositivTree) { InpPosTerms.AddLast(GetTermByCode(code, iTotalLevels)); } int iLevelCounter = 0; // while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels)) { HashSet<UInt64> X2PositivTree = new HashSet<UInt64>(); Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms, SkleivPosTerms, iLevelCounter, iTotalLevels); if ((X1NegativTree != null) && (X1NegativTree.Count != 0)) { HashSet<UInt64> X2NegativTree = new HashSet<UInt64>(); Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms, SkleivNegTerms, iLevelCounter, iTotalLevels); // X1NegativTree.Clear(); X1NegativTree = X2NegativTree; } // X1PositivTree.Clear(); X1PositivTree = X2PositivTree; iLevelCounter++; GC.Collect(); } } else { TreeFuncTerm X1PositivTree = new TreeFuncTerm(); DeleteDublicatingTerms(PositivTerms, X1PositivTree); TreeFuncTerm X1NegativTree = null; if (NegativTerms != null) { X1NegativTree = new TreeFuncTerm(); DeleteDublicatingTerms(NegativTerms, X1NegativTree); // for (TreeFuncTerm.TreeNodeEnd x1 = X1PositivTree.EnumerationInit(); x1 != null; x1 = X1PositivTree.EnumerationNextNode()) { if (!X1NegativTree.Contains(X1PositivTree.EnumerationTerm)) continue; // - PositivTerms NegativTerms int iPos_Count = PositivTerms.Count(p => IsEqualTerms(p, X1PositivTree.EnumerationTerm)); int iNeg_Count = NegativTerms.Count(p => IsEqualTerms(p, X1PositivTree.EnumerationTerm)); if (iPos_Count > iNeg_Count) { X1NegativTree.Remove(X1PositivTree.EnumerationTerm); } else if (iPos_Count < iNeg_Count) { X1PositivTree.Remove(X1PositivTree.EnumerationTerm); } else //if (iPos_Count == iNeg_Count) { X1PositivTree.Remove(X1PositivTree.EnumerationTerm); X1NegativTree.Remove(X1PositivTree.EnumerationTerm); } } // for (TreeFuncTerm.TreeNodeEnd x1 = X1NegativTree.EnumerationInit(); x1 != null; x1 = X1NegativTree.EnumerationNextNode()) { InpNegTerms.AddLast((byte[])X1NegativTree.EnumerationTerm.Clone()); } } // for (TreeFuncTerm.TreeNodeEnd X1Term = X1PositivTree.EnumerationInit(); X1Term != null; X1Term = X1PositivTree.EnumerationNextNode()) { InpPosTerms.AddLast((byte[])X1PositivTree.EnumerationTerm.Clone()); } int iLevelCounter = 0; // while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels)) { TreeFuncTerm X2PositivTree = new TreeFuncTerm(); Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms, SkleivPosTerms, iLevelCounter); if ((X1NegativTree != null) && (X1NegativTree.Count != 0)) { TreeFuncTerm X2NegativTree = new TreeFuncTerm(); Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms, SkleivNegTerms, iLevelCounter); // X1NegativTree.Clear(); X1NegativTree = X2NegativTree; } // X1PositivTree.Clear(); X1PositivTree = X2PositivTree; iLevelCounter++; GC.Collect(); } } // ReduceRedundancyTerms(InpPosTerms, SkleivPosTerms, OutPos); // ReduceRedundancyTerms(InpNegTerms, SkleivNegTerms, OutNeg); } // public void Start(IEnumerable<byte[]> TermsInput) { LogicFuncMinimize(TermsInput, _result.Terms, null, null); } // public void Start(IEnumerable<byte[]> TermsInput, IEnumerable<byte[]> NegativTerms) { LogicFuncMinimize(TermsInput, _result.Terms, NegativTerms, _resultNeg.Terms); } // public void Start(IEnumerable<char[]> TermsInput) { Start(TermsInput.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray())); } // public void Start(IEnumerable<char[]> TermsInput, IEnumerable<char[]> NegativTerms) { Start(TermsInput.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray()), NegativTerms.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray())); } // public void Start(IEnumerable<bool[]> TermsInput) { Start(TermsInput.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray())); } // public void Start(IEnumerable<bool[]> TermsInput, IEnumerable<bool[]> NegativTerms) { Start(TermsInput.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray()), NegativTerms.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray())); } public void PrintResult() { Console.WriteLine("--------Otvet-------"); char[] pTermSymbs = new char[] { '0', '1', '*' }; foreach (byte[] Term in _result.Terms) { for (int j = 0; j < Term.Length; j++) { Console.Write(pTermSymbs[Term[j]].ToString() + " "); } Console.WriteLine(); } } }
La classe Quine_McCluskey est une implémentation de cet algorithme qui utilise d'autres classes et interfaces: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Pour démarrer l'optimisation, vous devez appeler l'une des méthodes Start surchargées, qui appelle la fonction LogicFuncMinimize, où, en fait, l'algorithme de minimisation est implémenté. Le mécanisme de minimisation est implémenté en deux versions:
• Utilisation du conteneur .NET SortedSet pour stocker et rechercher des termes.
• sans utiliser de conteneurs .NET basés sur l'arborescence ternaire TreeFuncTerm.
En termes de vitesse, ces deux options sont à peu près égales (avec les conteneurs .NET, peut-être un peu plus rapides, mais pas toujours), mais la nécessité d'implémenter TreeFuncTerm est due à plusieurs facteurs:
• La première option, basée sur des codes de hachage d'entiers 64 bits et une recherche dans le dictionnaire SortedSet .NET, ne fonctionne correctement qu'avec le nombre de variables d'entrée en termes jusqu'à 40, et avec un nombre plus grand, elle dépasse la grille de codes de hachage d'entiers 64 bits, utilisé pour le fonctionnement des conteneurs. En effet, puisque la logique ternaire est utilisée en termes collés à l'intérieur de l'algorithme, alors avec le nombre de variables d'entrée égal à 41, la valeur maximale du code de hachage
dépasse déjà la valeur maximale
-1, qui peut être écrit dans une variable 64 bits. Avec plus de variables, une option est utilisée basée sur l'arbre de recherche ternaire TreeFuncTerm de l'auteur.
• Il est nécessaire de vérifier le fonctionnement de l'implémentation sur les conteneurs .NET avec une autre implémentation indépendante de celle-ci, libre d'eux.
• Vous avez juste besoin d'une option exempte de conteneurs .NET, qui pourrait être facilement implémentée sur des plateformes où il n'y a pas de plateforme .NET (par exemple, dans les microcontrôleurs, les FPGA, etc.).
Le fonctionnement de l'arborescence de recherche TreeFuncTerm est basé sur la configuration des liens vers les classes TreeNodeMiddle et TreeNodeEnd, qui sont des implémentations de l'interface TreeNodeBase. La classe TreeNodeMiddle est un nœud intermédiaire de l'arbre et la classe TreeNodeEnd est l'extrémité de feuille de l'arbre. À l'aide des fonctions EnumerationInit () et EnumerationNextNode (), un mécanisme non récursif pour énumérer toutes les feuilles de TreeNodeEnd est implémenté dans l'arborescence. La fonction EnumerationInit () initialise l'énumération et renvoie la première feuille de l'arborescence. La fonction EnumerationNextNode () renvoie la prochaine feuille d'arbre ou NULL s'il n'y a plus de feuilles pour la sélection. De plus, la structure interne auxiliaire EnumerationTerm, qui reflète la position du «curseur» de recherche à l'intérieur de l'arbre, est également le terme code de la feuille trouvée dans la logique ternaire {0,1,2}. Il est à noter que l'ordre de sélection des feuilles de l'arbre ne coïncide pas avec l'ordre de leur addition.
L'algorithme à des fins fonctionnelles peut être divisé en trois étapes.
- Préparation. Pour résoudre le problème ci-dessus d'éliminer l'énumération des options de définitions supplémentaires dans l'implémentation considérée, l'entrée de l'algorithme dans la fonction LogicFuncMinimize reçoit deux ensembles de données initiaux PositivTerms et NegativTerms, sur lesquels la fonction optimisée accepte respectivement les valeurs true (TRUE, 1) et false (FALSE, 0). Tout d'abord, ces listes sont vérifiées pour la cohérence des données source. Il est nécessaire que chacun des ensembles de données soit garanti pour ne contenir que des termes uniques qui ne sont présents que dans l'une des listes. Pour garantir cela, chaque terme d'entrée unique est analysé et le nombre d'entrées dans chacune des listes source est trouvé. Si le terme apparaît dans les deux listes, il ne reste que dans la liste dans laquelle il apparaît davantage et est supprimé de l'autre. Si le terme apparaît également dans chacune des listes, il est supprimé des deux listes, ce qui garantit l'unicité.
- Collage. Ensuite, un cycle itératif de collage des termes d'entrée est effectué. A chaque itération, en termes collés, un signe * de la position collée est ajouté. Par conséquent, le nombre d'itérations ne peut pas être supérieur au nombre de variables N. Contrairement à l'implémentation précédente, la fonction Skleivanie pour coller des termes d'entrée a la capacité de coller non seulement avec des termes de sa liste, mais aussi en l'absence d'un terme avec une différence également avec les termes dits "virtuels". Par termes «virtuels», nous entendons des termes définis artificiellement qui ne se trouvent dans aucune des listes de termes d'un ensemble du niveau actuel. Mais le collage n'est possible que si le terme «virtuel» ne couvre pas un seul terme de l'ensemble initial de la liste opposée.
La fonction Skleivanie est appelée pour traiter deux fois les listes à chaque itération de sorte que dans le premier appel, la signification de l'utilisation des listes PositivTerms et NegativTerms coïncide avec leur contenu réel, et dans le deuxième appel, les listes PositivTerms et NegativTerms sont échangées en termes d'utilisation, c'est-à-dire, on considère que La liste PositivTerms contient des termes négatifs et la liste NegativTerms contient des termes positifs:
Skleivanie (X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, ...);
Skleivanie (X1NegativTree, ..., X1PositivTree, ..., null, ...);
Ainsi, un collage simultané interdépendant des termes de deux listes se produit.
Si pour le terme il n'y a pas d'autre terme qui soit différent de lui dans une seule position, ni réel ni virtuel, c'est-à-dire que le terme ne colle avec personne, alors il est considéré comme l'un des résultats de l'étape 1 de l'algorithme, il est exclu des travaux ultérieurs et va à l'entrée de l'étape 2 de l'algorithme implémenté dans la procédure ReduceRedundancyTerms. Les termes non collés sont envoyés à la sortie de l'algorithme uniquement lors de cet appel à la fonction Skleivanie, pour lequel la signification de l'utilisation des listes PositivTerms et NegativTerms coïncide avec leur remplissage réel, c'est-à-dire lors du premier appel. - Abréviation. Les termes collés redondants sont rejetés dans ReduceRedundancyTerms à l'aide d'un algorithme pour résoudre approximativement le problème de la couverture de l'ensemble d'origine avec des sous-ensembles de longueur variable. La couverture, qui est proche de la plus courte, est fournie par l'algorithme de conversion de la table de couverture (TP), basé sur la méthode «colonne minimale - ligne maximale» (qui peut être consultée, par exemple, ici http://www.studfiles.ru/preview/5175815/page:4 ) .
La logique approximative de son travail est la suivante:
0. La table d'origine est considérée comme le TP transformé actuel, l'ensemble des lignes de couverture est vide;
1. La colonne avec le moins d'unités est mise en surbrillance dans le tableau actuel. Parmi les lignes contenant des unités dans cette colonne, une avec le plus grand nombre d'unités est mise en évidence. Cette ligne est incluse dans la couverture, la table actuelle est réduite en supprimant toutes les colonnes dans lesquelles la ligne sélectionnée a une unité.
2. S'il n'y a pas de colonnes barrées dans le tableau, l'étape 1 est exécutée, sinon la couverture est construite. Remarque: Lors du calcul du nombre d'unités dans une ligne, les unités dans les colonnes non marquées sont prises en compte.
Cet algorithme fonctionne assez rapidement et donne un résultat presque optimal.
Pour tester le fonctionnement de l'algorithme, il est proposé d'utiliser la fonction de test TestQuineMcCluskeyRandomPart, qui, sur l'ensemble des termes possibles, est sélectionne aléatoirement uniquement la partie donnée 0 <dPart <= 1 (est un paramètre de la fonction), pour laquelle l'optimisation est effectuée. Avec le paramètre dPart <1, un ensemble tronqué de termes d'entrée sera obtenu et avec dPart = 1, un ensemble complet de données d'entrée sera obtenu.
TestQuineMcCluskeyRandomPart (cliquez pour voir) public static void TestQuineMcCluskeyRandomPart(int iVariableAmount, double dPart=1) { if (dPart < 0) throw new ArgumentException(" dPart 0 1"); if (dPart > 1) dPart = 1; // ulong iTotalCombines = (ulong)1 << iVariableAmount; LinkedList<byte[]> pTrueCol = new LinkedList<byte[]>(); LinkedList<byte[]> pFalseCol = new LinkedList<byte[]>(); HashSet<ulong> pUsedTerms = new HashSet<ulong>(); Random rnd = new Random(); byte[] buf = new byte[8]; while (pUsedTerms.LongCount() < (iTotalCombines * dPart)) { rnd.NextBytes(buf); ulong iCurValue = (ulong)BitConverter.ToInt64(buf, 0) % iTotalCombines; if (pUsedTerms.Contains(iCurValue)) { // - do { iCurValue = ++iCurValue % iTotalCombines; } while (pUsedTerms.Contains(iCurValue)); } pUsedTerms.Add(iCurValue); byte[] sLine = new byte[iVariableAmount]; for (int i = 0; i < iVariableAmount; i++) { sLine[i] += (byte)(iCurValue % 2); iCurValue >>= 1; } if (rnd.Next(2) != 0) { pTrueCol.AddLast(sLine); } else { pFalseCol.AddLast(sLine); } } // DateTime DtStart = DateTime.Now; Console.WriteLine(" - " + DtStart.ToLongTimeString()); Quine_McCluskey Logic = new Quine_McCluskey(); Logic.Start(pTrueCol, pFalseCol); DateTime DtEnd = DateTime.Now; Logic.PrintResult(); Console.WriteLine(" - " + DtStart.ToLongTimeString()); Console.WriteLine(" - " + DtEnd.ToLongTimeString()); TimeSpan Elapsed = DtEnd - DtStart; Console.WriteLine(" - " + String.Format("{0:00}:{1:00}:{2:00}", Elapsed.Hours, Elapsed.Minutes, Elapsed.Seconds)); // int iErrorsCounter = 0; foreach (byte[] kvp in pTrueCol) { if (Logic.Result.Calculate(kvp) != true) iErrorsCounter++; } foreach (byte[] kvp in pFalseCol) { if (Logic.Result.Calculate(kvp) != false) iErrorsCounter++; } Console.WriteLine("- = " + pUsedTerms.Count); Console.WriteLine("- = " + Logic.Result.Terms.Count); Console.WriteLine("- = " + iErrorsCounter); Console.ReadLine(); }
À la suite de la fonction de test, le nombre de termes dans la forme normale disjonctive minimale et le nombre d'erreurs le couvrant avec l'ensemble de termes d'origine sont calculés.
En conclusion, je voudrais noter qu'en pratique, cette implémentation de l'algorithme s'est révélée être un moyen efficace et fiable de minimiser les fonctions logiques définies par deux ensembles de termes incomplets sur lesquels la fonction logique prend les valeurs VRAI et FAUX, respectivement. Bien entendu, cette implémentation peut également être utilisée sous la forme classique dans le cas d'une fonction logique d'entrée complètement définie, lorsque seule l'une ou l'autre liste de termes est entrée. Comme inconvénient, il est nécessaire de vérifier dans la fonction Skleivanie qu'il n'y a pas d'erreurs de couverture pour chaque terme virtuel de la liste complète des termes source à chaque itération de l'algorithme, ce qui entraîne des coûts de temps importants avec un grand nombre de termes d'entrée.