👨🏾‍🌾 🙆🏼 ⏫ Implementación de minimización de funciones lógicas por el método Quine \ McCluskey con un conjunto de entrada incompleto 👩🏻‍🔬 🧀 🦏

Este artículo es, en cierta medida, una continuación de mi artículo sobre la minimización de las funciones lógicas por el método Quine-Mac'Klaski ( https://habr.com/post/328506 ). Consideró un caso con funciones lógicas completamente definidas (aunque esto no se mencionaba directamente en él, sino que solo estaba implícito). En realidad, tal caso es bastante raro cuando el número de variables de entrada es pequeño. Se definen parcial o incompletamente las funciones lógicas cuyos valores se dan solo para la parte Q del conjunto completo P =

2^{N}

$2 ^ N$ posibles conjuntos (términos) de sus argumentos (variables) del número N , es decir, Q <P. Esta situación se encuentra en la práctica en la mayoría de los casos de aplicación de algoritmos para optimizar funciones lógicas. De hecho, por ejemplo, si el número de variables de entrada es N = 30, que es un caso ordinario, por ejemplo, en los mercados financieros, entonces el volumen de la muestra de capacitación de entrada debe ser del orden de

2^{30}

$2 ^ {30}$ >

10^{9}

$10 ^ 9$ Términos únicos únicos. Dicha matriz de datos no se encuentra en todas las organizaciones incluso muy grandes, sin mencionar a los individuos, es decir, esta ya es la esfera de BigData, el uso de centros de datos, etc.

Por lo tanto, en la práctica, las funciones lógicas minimizadas con mayor frecuencia no se determinarán por completo simplemente debido a la falta de la cantidad requerida de datos acumulados o debido a varias otras razones objetivas (por ejemplo, no hay suficiente espacio para almacenarlas). Surge la pregunta sobre la posibilidad de "eludir" este problema cuando se utiliza un algoritmo que funciona con un conjunto completamente definido de funciones lógicas de término, como, por ejemplo, de mi artículo anterior.

La práctica estándar en este caso es determinar el conjunto de entrada incompleto de valores variables (término) al completo para que dé un resultado óptimo para el conjunto de datos existente. Pero, en este caso, existe un problema al enumerar todas las variantes posibles de definiciones adicionales, cuyo número total es V =

2^{P - Q}

$2 ^ {P-Q}$ seleccionar la mejor opción para una definición adicional de acuerdo con un criterio dado. Obviamente, para los valores realmente utilizados de Q y P, el número de opciones clasificadas para definiciones adicionales es astronómicamente grande y este enfoque no puede implementarse en la práctica debido al inmenso costo computacional.

Por lo tanto, se necesita un enfoque diferente que elimine la necesidad de enumerar varias opciones para definiciones adicionales. Por lo tanto, es necesario modernizar el algoritmo original, que inicialmente funciona solo con un conjunto de entrada completamente definido, de modo que también pueda funcionar con un conjunto truncado. Es una implementación del algoritmo que se propone en este artículo, basado en el hecho de que durante el proceso de minimización se procesan simultáneamente dos listas incompletas de términos, en los que la función se especifica como FALSO (0) y VERDADERO (1).

Desde el punto de vista del aprendizaje automático, el algoritmo Quine-Mac'Klaski implementa el paradigma de aprendizaje con el maestro cuando los valores de salida correspondientes de la función objetivo están involucrados en el proceso de aprendizaje (en este caso, minimización) simultáneamente. Permítanme recordarles que el principio de funcionamiento del método básico de Quine-Mac'Klaski según la teoría consta de dos etapas principales:

Etapa. Encontrar todos los términos simples de LF usando reglas de pegado (leyes):
a) (A y B)? (A y B) A
b) (A? B) y (A ?! B)? A
¿dónde y es la operación lógica Y? - operación de "OR" lógico; - operación de negación lógica "NO". De estas fórmulas se deduce que dos términos se unen si difieren entre sí solo en una de las posiciones de las variables. En la posición donde los dos términos difieren entre sí, se coloca el signo "*". Por lo tanto, el alfabeto en términos pegados en comparación con el original se expande a tres valores:
• 0 => falso;
• 1 => verdadero;
• 2 => variable pegada (*).
Etapa. Minimización del número de términos pegados obtenidos después de la primera etapa, como un problema para encontrar la cobertura óptima del conjunto inicial de términos con la cantidad Q. Es decir, dado que cada término de salida cubre solo un cierto subconjunto de los términos iniciales, es necesario elegir un conjunto mínimo de términos de salida que se identifiquen con con ellos, los subconjuntos de diferentes longitudes en el agregado cubrieron completamente todos los términos de entrada iniciales. Recubrimiento en este caso significa que la operación bit a bit de la disyunción del término de salida sobre el término de entrada dio un valor verdadero. Digamos que el término pegado de salida tiene la siguiente forma: 10 * 0110 *.
Luego cubre el término 10101100:
10 * 0110 * y 10101100 = VERDADERO
pero no cubre el término 00101100:
10 * 0110 * y 00101100 = FALSO
Es decir, el término de entrada y la salida deben coincidir en todas partes, excepto en las posiciones donde hay un símbolo "*"; en esta posición, la variable del término de entrada puede tomar cualquier valor, porque en esta posición, la variable se excluye de la consideración.

El código de implementación es el siguiente (haga clic para ver):

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 clase Quine_McCluskey es una implementación de este algoritmo que utiliza otras clases e interfaces: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Para comenzar la optimización, debe llamar a uno de los métodos de Inicio sobrecargados, que llama a la función LogicFuncMinimize, donde, de hecho, se implementa el algoritmo de minimización. El mecanismo de minimización se implementa en dos versiones:
• Uso del contenedor .NET SortedSet para almacenar y buscar términos.
• sin usar contenedores .NET basados en el árbol ternario TreeFuncTerm.

En términos de velocidad, estas dos opciones son aproximadamente iguales (con contenedores .NET, quizás un poco más rápido, pero no siempre), pero la necesidad de implementar TreeFuncTerm se debe a varios factores:
• La primera opción, basada en códigos hash de enteros de 64 bits y una búsqueda en el diccionario SortedSet .NET, funciona correctamente solo con el número de variables de entrada en términos de hasta 40, y con un número mayor va más allá de la cuadrícula de códigos hash de enteros de 64 bits, utilizado para la operación de contenedores. De hecho, dado que la lógica ternaria se usa en términos pegados dentro del algoritmo, entonces con el número de variables de entrada igual a 41, el valor máximo del código hash

3^{41}

$3 ^ {41}$ ya excede el valor máximo

2^{64}

$2 ^ {64}$ -1, que se puede escribir en una variable de 64 bits. Con más variables, se utiliza una opción basada en el árbol de búsqueda ternario del autor TreeFuncTerm.
• Es necesario verificar el funcionamiento de la implementación en contenedores .NET con otra implementación independiente de ella, libre de ellos.
• Solo necesita una opción que esté libre de contenedores .NET, que podría implementarse fácilmente en plataformas donde no hay una plataforma .NET (por ejemplo, en microcontroladores, FPGA, etc.).
El funcionamiento del árbol de búsqueda TreeFuncTerm se basa en la configuración de enlaces a las clases TreeNodeMiddle y TreeNodeEnd, que son implementaciones de la interfaz TreeNodeBase. La clase TreeNodeMiddle es un nodo intermedio del árbol, y la clase TreeNodeEnd es el extremo de la hoja del árbol. Usando las funciones EnumerationInit () y EnumerationNextNode (), se implementa un mecanismo no recursivo para enumerar todas las hojas de TreeNodeEnd en el árbol. La función EnumerationInit () inicializa la enumeración y devuelve la primera hoja del árbol. La función EnumerationNextNode () devuelve la siguiente hoja del árbol o NULL si no hay más hojas para la selección. Además, la estructura interna auxiliar EnumerationTerm, que refleja la posición del "cursor" de búsqueda dentro del árbol, es también el código de término de la hoja encontrada en la lógica ternaria {0,1,2}. Cabe señalar que el orden de selección de las hojas del árbol no coincide con el orden de agregarlas.

El algoritmo para fines funcionales se puede dividir en tres etapas.

Preparación Para resolver el problema anterior de eliminar la enumeración de opciones para definiciones adicionales en la implementación en consideración, la entrada del algoritmo a la función LogicFuncMinimize recibe dos conjuntos de datos iniciales PositivTerms y NegativTerms, en los cuales la función optimizada acepta valores verdaderos (VERDADERO, 1) y falso (FALSO, 0), respectivamente. En primer lugar, estas listas se comprueban por la coherencia de los datos de origen. Es necesario que cada uno de los conjuntos de datos contenga solo términos únicos que estén presentes solo en cualquiera de las listas. Para garantizar esto, se escanea cada término de entrada único y se encuentra el número de entradas en cada una de las listas de origen. Si el término aparece en ambas listas, solo permanece en la lista en la que aparece más y se elimina de la otra. Si el término aparece en cada una de las listas con la misma frecuencia, entonces se elimina de ambas listas, lo que garantiza la unicidad.
Vinculación A continuación, se realiza un ciclo iterativo para pegar los términos de entrada. En cada iteración, en términos pegados, se agrega un signo * de la posición pegada. Por lo tanto, el número de iteraciones no puede ser mayor que el número de variables N. A diferencia de la implementación anterior, la función Skleivanie para pegar términos de entrada tiene la capacidad de pegar no solo con términos de su lista, sino también en ausencia de un término con una diferencia también con los llamados términos "virtuales". Por términos "virtuales" nos referimos a términos definidos artificialmente que no se encuentran en ninguna de las listas de términos de un conjunto del nivel actual. Pero el pegado solo es posible si el término "virtual" no cubre un solo término del conjunto inicial de la lista opuesta.
La función Skleivanie se llama para procesar listas en cada iteración dos veces, de modo que en la primera llamada el significado del uso de las listas PositivTerms y NegativTerms coincide con su contenido real, y en la segunda llamada, las listas PositivTerms y NegativTerms se intercambian en términos de uso, es decir, se considera que La lista PositivTerms contiene términos negativos y la lista NegativTerms contiene términos positivos:
Skleivanie (X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, ...);
Skleivanie (X1NegativTree, ..., X1PositivTree, ..., null, ...);
Por lo tanto, se produce un pegado simultáneo interdependiente de los términos de dos listas.
Si para el término no hay otro término que sea diferente de él en una sola posición, ni real ni virtual, es decir, el término no se adhiere a nadie, entonces se considera uno de los resultados del paso 1 del algoritmo, se excluye de un trabajo adicional en él y continúa a la entrada de la etapa 2 del algoritmo implementado en el procedimiento ReduceRedundancyTerms. Los términos no pegados se envían a la salida del algoritmo solo en esa llamada a la función Skleivanie, para lo cual el significado de usar las listas PositivTerms y NegativTerms coincide con su llenado real, es decir, en la primera llamada.
Abreviatura Los términos pegados redundantes se descartan en los Términos de reducción de redundancia utilizando un algoritmo para resolver de manera aproximada el problema de cubrir el conjunto original con subconjuntos de longitud variable. La cobertura, que es cercana a la más corta, es proporcionada por el algoritmo para convertir la tabla de cobertura (TP), basado en el método de "columna mínima - fila máxima" (que se puede ver, por ejemplo, aquí http://www.studfiles.ru/preview/5175815/page:4 ) .
La lógica aproximada de su trabajo es la siguiente:
0. La tabla original se considera el TP transformado actual, el conjunto de líneas de cobertura está vacío;
1. La columna con la menor cantidad de unidades se resalta en la tabla actual. Entre las filas que contienen unidades en esta columna, se resalta una con el mayor número de unidades. Esta fila se incluye en la cobertura, la tabla actual se reduce al eliminar todas las columnas en las que la fila seleccionada tiene una unidad.
2. Si no hay columnas tachadas en la tabla, se realiza el paso 1, de lo contrario, se construye la cobertura. Nota: Al calcular el número de unidades en una fila, se tienen en cuenta las unidades en columnas sin marcar.
Este algoritmo funciona lo suficientemente rápido y da un resultado cercano al óptimo.
Para probar el funcionamiento del algoritmo, se propone utilizar la función de prueba TestQuineMcCluskeyRandomPart, que, del conjunto total de términos posibles, es $2 ^ N$ selecciona aleatoriamente solo la parte dada 0 <dPart <= 1 (es un parámetro de la función), para la cual se realiza la optimización. Con el parámetro dPart <1, se obtendrá un conjunto truncado de términos de entrada, y con dPart = 1, se obtendrá un conjunto completo de datos de entrada.

TestQuineMcCluskeyRandomPart (haga clic para ver)

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

Como resultado de la función de prueba, se calcula el número de términos en la forma normal mínima disyuntiva y el número de errores que lo cubren con el conjunto original de términos.

En conclusión, me gustaría señalar que, en la práctica, esta implementación del algoritmo ha demostrado ser un medio eficaz y confiable de minimizar las funciones lógicas definidas por dos conjuntos incompletos de términos en los que la función lógica toma valores VERDADERO y FALSO, respectivamente. Por supuesto, esta implementación también se puede usar en la forma clásica en el caso de una función lógica de entrada completamente definida, cuando solo se ingresa una u otra lista de términos. Como inconveniente, es necesario verificar en la función Skleivanie que no hay errores de cobertura para cada término virtual de la lista completa de términos fuente en cada iteración del algoritmo, lo que conduce a costos de tiempo significativos con una gran cantidad de términos de entrada.

Implementación de minimización de funciones lógicas por el método Quine \ McCluskey con un conjunto de entrada incompleto

More articles: