🕛 👲🏿 🎅🏼 使用不完整输入集的Quine \ McCluskey方法实现逻辑功能的最小化 ⏰ 🧒🏼 🛒

在某种程度上，本文是我有关Quine-Mac'Klaski方法（ https://habr.com/post/328506 ）最小化逻辑功能的文章的续篇。它考虑了具有完全定义的逻辑功能的情况（尽管在此并未直接提及，而只是暗示）。实际上，当输入变量的数量很少时，这种情况很少发生。部分或不完全定义的逻辑函数的值仅针对完整集合P中的Q部分给出

2^{N}

$2 ^ N$ N个参数（变量）的可能集合（项），即Q <P。在大多数情况下，在应用算法优化逻辑功能的情况下，都会遇到这种情况。确实，例如，如果输入变量的数量为N = 30（这在金融市场中是常见情况），那么输入训练样本的数量应为

2^{30}

$2 ^ {30}$ >

10^{9}

$10 ^ 9$ 独特的独特条款。在每个甚至非常大的组织中都找不到这样的数据数组，更不用说个人了，也就是说，这已经是BigData的领域，数据中心的使用等。

因此，实际上，仅仅由于缺少所需的累积数据量或由于各种其他客观原因（例如，没有足够的空间来存储它们），通常不会完全确定最小化的逻辑功能。当使用一种算法与完全定义的术语逻辑函数集一起工作时（例如，来自我之前的文章），就出现了“规避”此问题的可能性的问题。

在这种情况下，标准做法是将不完整的变量（项）值输入集确定为完整的值集，以便为现有数据集提供最佳结果。但是，在这种情况下，存在枚举附加定义的所有可能变体的问题，其总数为V =

2^{P - Q}

$2 ^ {P-Q}$ 根据给定的标准为附加定义选择最佳选项。显然，对于Q和P的实际使用值，用于附加定义的排序选项的数量在天文上是很大的，并且由于巨大的计算成本，该方法在实践中无法实现。

因此，需要一种不同的方法来消除为附加定义列举各种选项的需要。因此，有必要对原始算法进行现代化，该算法最初仅适用于完全定义的输入集，以便它也可以适用于截断的集。本文提出的算法就是这种实现方式，其基于以下事实：在最小化过程中，会同时处理两个不完整的术语列表，在该列表中将函数指定为FALSE（0）和TRUE（1）。

从机器学习的角度来看，当目标函数的相应输出值同时参与学习过程（在这种情况下为最小化）时，Quine-Mac'Klaski算法与教师一起实施学习范例。让我提醒您，根据该理论，基本Quine-Mac'Klaski方法的操作原理包括两个主要阶段：

舞台。使用粘合规则（定律）查找所有简单的LF术语：
a）（A和B）？（A＆！B）？ A;
b）（A？B）和（A ?! B）？ A;
逻辑与运算符＆在哪里？ -逻辑“或”的运算；！ -逻辑否定“ NOT”的操作。从这些公式得出的结论是，如果两个术语仅在变量的位置之一彼此不同，则将它们粘合在一起。在两个术语互不相同的位置，标有“ *”。因此，与原始字母相比，胶合字母的字母扩展为三个值：
•0 =>否；
•1 => true；
•2 =>粘合变量（*）。
舞台。最小化在第一阶段之后获得的插入项的数量，这是找到数量为Q的初始项的最佳覆盖范围的问题。也就是说，由于每个输出项仅覆盖源项的特定子集，因此有必要选择一组最小的输出项使用它们，集合中不同长度的子集完全覆盖了所有初始输入项。在这种情况下，涂层意味着输出项与输入项的相除的按位运算给出了真值。假设输出粘合术语具有以下形式：10 * 0110 *。
然后涵盖了术语10101100：
10 * 0110 *和10101100 = TRUE
但不涵盖条款00101100：
10 * 0110 *＆00101100 =否
也就是说，除了有“ *”符号的位置以外，输入项和输出项在所有地方都必须重合-在此位置，输入项的变量可以取任何值，因为在这个位置，变量被排除在考虑范围之外。

实现代码如下（单击查看）：

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(); } } }

Quine_McCluskey类是使用其他类和接口的该算法的实现：Dnf，TreeNodeBase，TreeNodeMiddle，TreeNodeEnd，TreeFuncTerm。要开始优化，您需要调用重载的Start方法之一，该方法调用LogicFuncMinimize函数，实际上在其中实现了最小化算法。最小化机制有两种版本：
•使用.NET SortedSet容器存储和搜索术语。
•不使用基于TreeFuncTerm三叉树的.NET容器。

在速度方面，这两个选项大致相等（对于.NET容器，可能更快一些，但并非总是如此），但是实现TreeFuncTerm的需要归因于以下几个因素：
•第一个选项基于64位整数哈希码并在SortedSet .NET词典中进行搜索，仅在输入变量的数量最多为40的情况下才能正确使用，而更大的数字则超出了64位整数哈希码网格，用于容器操作。确实，由于三元逻辑在算法内部以胶合形式使用，因此输入变量的数量等于41，即哈希码的最大值

3^{41}

$3 ^ {41}$ 已经超过最大值

2^{64}

$2 ^ {64}$ -1，可以将其写入64位变量。使用更多变量时，将基于作者的三元搜索树TreeFuncTerm使用一个选项。
•有必要检查.NET容器上实现的运行情况，并与另一个独立于它的实现进行检查。
•您只需要一个没有.NET容器的选项，就可以在没有.NET平台的平台上轻松实现该选项（例如，在微控制器，FPGA等中）。
TreeFuncTerm搜索树的操作基于对TreeNodeMiddle和TreeNodeEnd类的链接的配置，这些类是TreeNodeBase接口的实现。 TreeNodeMiddle类是树的中间节点，而TreeNodeEnd类是树的叶端。使用EnumerationInit（）和EnumerationNextNode（）函数，在树中实现了一种非递归机制，该机制用于枚举TreeNodeEnd的所有叶子。 EnumerationInit（）函数初始化枚举并返回树中的第一个叶子。 EnumerationNextNode（）函数返回下一个树叶，如果没有更多叶子可供选择，则返回NULL。此外，辅助内部结构EnumerationTerm反映了树中搜索“光标”的位置，也是三元逻辑{0,1,2}中找到的工作表的术语代码。应当注意，从树上选择叶子的顺序与将叶子添加到树上的顺序不一致。

用于功能目的的算法可以分为三个阶段。

准备。 为了解决上述在考虑中的实现中消除对其他定义的选项枚举的问题，向LogicFuncMinimize函数的算法输入接收两个初始数据集PositivTerms和NegativTerms，优化后的函数分别在其中接受true（TRUE，1）和false（FALSE，0）值。首先，检查这些列表中源数据的一致性。必须保证每个数据集只包含仅在任何一个列表中都存在的唯一术语。为了保证这一点，将扫描每个唯一的输入项，并找到每个源列表中的条目数。如果该术语同时出现在两个列表中，则该术语仅保留在列表中，在该列表中出现更多，并从另一个列表中删除。如果该术语在每个列表中均等出现，则将其从两个列表中删除，以确保唯一性。
粘接。 接下来，执行用于粘贴输入项的迭代循环。在每次迭代中，以胶合形式添加胶合位置的一个符号*。因此，迭代次数不能大于变量N。与以前的实现方式相比，用于粘合输入项的Skleivanie函数不仅具有粘合其列表中的项的能力，而且还具有在不存在具有所谓“虚拟”项区别的条件的情况下粘合的能力。 “虚拟”术语是指在当前水平的一组术语列表中找不到的人为定义的术语。但是只有当“虚拟”术语不覆盖相反列表的初始集合中的单个术语时，才可以进行胶合。
调用Skleivanie函数在每次迭代中处理列表两次，因此在第一个调用中，使用PositivTerms和NegativTerms列表的含义与它们的实际内容相符，而在第二个调用中，PositivTerms和NegativTerms列表在用法上互换了，即认为PositivTerms列表包含否定项，而NegativTerms列表包含肯定项：
Skleivanie（X1PositivTree，...，X1NegativTree，...，SkleivTerms，...）;
Skleivanie（X1NegativTree，...，X1PositivTree，...，null，...）;
因此，两个列表项同时发生相互依存的粘合。
如果对于该术语，没有任何其他术语与它仅在一个位置上（真实或虚拟位置）不同，也就是说，该术语不会与任何人粘在一起，则认为该算法是步骤1的结果之一，将其从进一步的工作中排除并继续进行到在ReduceRedundancyTerms过程中实现的算法的第2阶段的输入。仅在对Skleivanie函数的调用中，非粘合项才出现在算法的输出中，为此，使用PositivTerms和NegativTerms列表的含义与它们的实际填充（即在第一次调用中）一致。
的缩写。 冗余胶合术语在ReduceRedundancyTerms中使用一种算法丢弃，用于近似解决用可变长度子集覆盖原始集合的问题。转换范围表（TP）的算法基于“最小列-最大行”方法提供了最短的覆盖范围（例如，可以在此处http://www.studfiles.ru/preview/5175815/page:4 ）。
他的工作大致逻辑如下：
0.原始表被认为是当前转换的TP，覆盖线集合为空；
1.单位最少的列在当前表中突出显示。在此列中包含单位的行中，突出显示单位最多的行。该行包括在coverage中，通过删除所选行具有单位的所有列来缩小当前表。
2.如果表中没有交叉的列，则执行步骤1；否则，将构建coverage。注意：在计算一行中的单位数时，将考虑未标记列中的单位。
该算法足够快地工作，并且给出接近最佳的结果。
为了测试算法的操作，建议使用测试函数TestQuineMcCluskeyRandomPart，在可能的条件总数中， $2 ^ N$ 仅随机选择给定的零件0 <dPart <= 1（是函数的参数），对其进行优化。在参数dPart <1的情况下，将获得一组截短的输入项，而在dPart = 1的情况下，将获得完整的输入数据集。

TestQuineMcCluskeyRandomPart（单击查看）

 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(); }

测试功能的结果是，计算出最小析取范式中的项数以及覆盖原始项集的误差数。

总之，我想指出的是，在实践中，该算法的实现已被证明是最小化由两个不完整术语集定义的逻辑函数的有效且可靠的方法，逻辑函数分别对这两个不完全术语集取TRUE和FALSE值。当然，在仅定义一项或另一项术语输入的情况下，在完全定义的输入逻辑功能的情况下，也可以以经典形式使用此实现。缺点是，有必要在Skleivanie函数中检查在算法的每次迭代中，整个源项列表的每个虚拟项都没有覆盖错误，这会导致大量输入项带来大量时间成本。

使用不完整输入集的Quine \ McCluskey方法实现逻辑功能的最小化

More articles: