Este artigo é, em certa medida, uma continuação do meu artigo sobre a minimização de funções lógicas pelo método Quine-Mac'Klaski (
https://habr.com/post/328506 ). Considerou um caso com funções lógicas completamente definidas (embora isso não tenha sido mencionado diretamente, mas apenas implícito). Na realidade, esse caso é bastante raro quando o número de variáveis de entrada é pequeno. Parcial ou incompletamente definidas, são funções lógicas cujos valores são fornecidos apenas para a parte Q do conjunto completo P =
conjuntos possíveis (termos) de seus argumentos (variáveis) do número
N , isto é, Q <P. Essa situação é encontrada na prática na maioria dos casos de aplicação de algoritmos para otimizar funções lógicas. De fato, por exemplo, se o número de variáveis de entrada for
N = 30, que é um caso comum, por exemplo, nos mercados financeiros, o volume da amostra de treinamento de entrada deve ser da ordem de
>
termos únicos únicos. Esse conjunto de dados não é encontrado em todas as grandes organizações, para não mencionar indivíduos, ou seja, essa já é a esfera do BigData, o uso de data centers, etc.
Portanto, na prática, na maioria das vezes, as funções lógicas minimizadas não serão completamente determinadas simplesmente devido à falta da quantidade necessária de dados acumulados ou devido a várias outras razões objetivas (por exemplo, não há espaço suficiente para armazená-las). Surge a pergunta sobre a possibilidade de "contornar" esse problema ao usar um algoritmo que funciona com um conjunto completamente definido de funções lógicas de termos, como, por exemplo, no meu artigo anterior.
A prática padrão neste caso é determinar o conjunto de entrada incompleto de valores de variável (termo) para o valor completo, de modo a fornecer um resultado ideal para o conjunto de dados existente. Mas, neste caso, há um problema na enumeração de todas as variantes possíveis de definições adicionais, cujo número total é V =
para selecionar a melhor opção para definição adicional de acordo com um determinado critério. Obviamente, para os valores realmente usados de Q e P, o número de opções classificadas para definições adicionais é astronomicamente grande e essa abordagem não pode ser implementada na prática devido ao imenso custo computacional.
Portanto, é necessária uma abordagem diferente que elimine a necessidade de enumerar várias opções para definições adicionais. Portanto, é necessário modernizar o algoritmo original, que inicialmente funciona apenas com um conjunto de entradas totalmente definido, para que ele também possa trabalhar com um conjunto truncado. Essa implementação do algoritmo é proposta neste artigo, com base no fato de que, no processo de minimização, duas listas incompletas de termos são processadas simultaneamente, nas quais a função é especificada como FALSE (0) e TRUE (1).
Do ponto de vista do aprendizado de máquina, o algoritmo Quine-Mac'Klaski implementa o paradigma de aprendizado com o professor quando os valores de saída correspondentes da função objetivo estão envolvidos no processo de aprendizado (neste caso, minimização) simultaneamente. Deixe-me lembrá-lo que o princípio de operação do método básico de Quine-Mac'Klaski, de acordo com a teoria, consiste em dois estágios principais:
- Stage. Localizando todos os termos LF simples usando regras de colagem (leis):
a) (A e B)? (A e B)? A;
b) (A? B) e (A ?! B)? A;
onde & é a operação lógica AND; - operação do "OR" lógico; - operação de negação lógica "NÃO". A partir dessas fórmulas, segue-se que dois termos são colados, se diferirem entre si apenas em uma das posições das variáveis. Na posição em que os dois termos diferem entre si, o sinal "*" é colocado. Assim, o alfabeto em termos colados em comparação com o original se expande para três valores:
0 => falso;
1 => verdadeiro;
• 2 => variável colada (*). - Stage. Minimização do número de termos colados obtidos após o primeiro estágio, como um problema de encontrar a cobertura ideal do conjunto inicial de termos com a quantidade Q. Ou seja, como cada termo de saída cobre apenas um determinado subconjunto dos termos iniciais, é necessário escolher um conjunto mínimo de termos de saída que sejam identificados com com eles, subconjuntos de diferentes comprimentos no agregado cobriam completamente todos os termos de entrada iniciais. O revestimento neste caso significa que a operação bit a bit da disjunção do termo de saída sobre o termo de entrada deu um valor verdadeiro. Digamos que o termo colado de saída tenha a seguinte forma: 10 * 0110 *.
Em seguida, abrange o termo 10101100:
10 * 0110 * e 10101100 = VERDADEIRO
mas não abrange o termo 00101100:
10 * 0110 * & 00101100 = FALSO
Ou seja, o termo de entrada e a saída devem coincidir em todos os lugares, exceto nas posições em que existe um símbolo "*" - nessa posição, a variável do termo de entrada pode assumir qualquer valor, porque nesta posição, a variável é excluída da consideração.
O código de implementação é o seguinte (clique para visualizar):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(); } } }
A classe Quine_McCluskey é uma implementação desse algoritmo que usa outras classes e interfaces: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Para iniciar a otimização, você precisa chamar um dos métodos Start sobrecarregados, que chama a função LogicFuncMinimize, onde o algoritmo de minimização é implementado. O mecanismo de minimização é implementado em duas versões:
• Usando o contêiner .NET SortedSet para armazenar e pesquisar termos.
• sem usar contêineres .NET com base na árvore ternária do TreeFuncTerm.
Em termos de velocidade, essas duas opções são aproximadamente iguais (com contêineres .NET, talvez um pouco mais rápidos, mas nem sempre), mas a necessidade de implementar o TreeFuncTerm se deve a vários fatores:
• A primeira opção, com base nos códigos de número inteiro de 64 bits e em uma pesquisa no dicionário SortedSet .NET, funciona corretamente apenas com o número de variáveis de entrada em termos de até 40 e, com um número maior, vai além da grade de código de número inteiro de 64 bits, usado para operação de contêiner. De fato, como a lógica ternária é usada em termos colados dentro do algoritmo, com o número de variáveis de entrada igual a 41, o valor máximo do código hash
já excede o valor máximo
-1, que pode ser gravado em uma variável de 64 bits. Com mais variáveis, uma opção é usada com base na árvore de pesquisa ternária do autor TreeFuncTerm.
• É necessário verificar a operação da implementação em contêineres .NET com outra implementação independente, livre deles.
• Você só precisa de uma opção livre de contêineres .NET, que pode ser facilmente implementada em plataformas onde não há plataforma .NET (por exemplo, em microcontroladores, FPGAs, etc.).
A operação da árvore de pesquisa TreeFuncTerm é baseada na configuração de links para as classes TreeNodeMiddle e TreeNodeEnd, que são implementações da interface TreeNodeBase. A classe TreeNodeMiddle é um nó intermediário da árvore e a classe TreeNodeEnd é o final da folha da árvore. Usando as funções EnumerationInit () e EnumerationNextNode (), um mecanismo não recursivo para enumerar todas as folhas de folhas de TreeNodeEnd é implementado na árvore. A função EnumerationInit () inicializa a enumeração e retorna a primeira folha na árvore. A função EnumerationNextNode () retorna a próxima folha da árvore ou NULL se não houver mais folhas para a seleção. Além disso, a estrutura interna auxiliar EnumerationTerm, que reflete a posição do “cursor” de busca dentro da árvore, também é o código de termo da planilha encontrada na lógica ternária {0,1,2}. Note-se que a ordem de seleção das folhas da árvore não coincide com a ordem de adicioná-las a ela.
O algoritmo para fins funcionais pode ser dividido em três estágios.
- Preparação. Para resolver o problema acima de eliminar a enumeração de opções para definições adicionais na implementação em consideração, a função LogicFuncMinimize recebe dois conjuntos de dados iniciais PositivTerms e NegativTerms, nos quais a função otimizada aceita valores true (TRUE, 1) e false (FALSE, 0), respectivamente. Antes de tudo, essas listas são verificadas quanto à consistência dos dados de origem. É necessário que seja garantido que cada um dos conjuntos de dados contenha apenas termos exclusivos presentes apenas em qualquer uma das listas. Para garantir isso, cada termo de entrada exclusivo é verificado e o número de entradas em cada uma das listas de fontes é encontrado. Se o termo aparecer nas duas listas, ele permanecerá apenas na lista em que aparece mais e será excluído da outra. Se o termo ocorrer em cada uma das listas com a mesma frequência, ele será removido das duas listas, o que garante exclusividade.
- Ligação. Em seguida, é executado um ciclo iterativo para colar termos de entrada. A cada iteração, em termos colados, um sinal * da posição colada é adicionado. Portanto, o número de iterações não pode ser maior que o número de variáveis N. Em contraste com a implementação anterior, a função Skleivanie para colar termos de entrada tem a capacidade de colar não apenas os termos de sua lista, mas também na ausência de um termo com uma diferença, também com os chamados termos "virtuais". Por termos "virtuais", entendemos termos definidos artificialmente que não são encontrados em nenhuma das listas de termos de um conjunto do nível atual. Porém, a colagem é possível apenas se o termo "virtual" não cobrir um único termo do conjunto inicial da lista oposta.
A função Skleivanie é chamada para processar listas em cada iteração duas vezes, de modo que, na primeira chamada, o significado do uso das listas PositivTerms e NegativTerms coincida com seu conteúdo real e, na segunda chamada, as listas PositivTerms e NegativTerms sejam trocadas em termos de uso, ou seja, considera-se que A lista PositivTerms contém termos negativos e a lista NegativTerms contém termos positivos:
Skleivanie (X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, ...);
Skleivanie (X1NegativTree, ..., X1PositivTree, ..., null, ...);
Assim, ocorre uma colagem interdependente simultânea dos termos de duas listas.
Se, para o termo, não houver outro termo diferente em apenas uma posição, nem real nem virtual, ou seja, o termo não se une a ninguém, é considerado um dos resultados da etapa 1 do algoritmo, é excluído de outros trabalhos e segue à entrada do estágio 2 do algoritmo implementado no procedimento ReduceRedundancyTerms. Termos não colados são enviados para a saída do algoritmo somente nessa chamada para a função Skleivanie, para a qual o significado do uso das listas PositivTerms e NegativTerms coincide com o preenchimento real, ou seja, na primeira chamada. - Abreviação. Os termos colados redundantes são descartados nos ReduceRedundancyTerms usando um algoritmo para resolver aproximadamente o problema de cobrir o conjunto original com subconjuntos de comprimento variável. A cobertura, que é a mais curta, é fornecida pelo algoritmo para converter a tabela de cobertura (TP), com base no método "coluna mínima - linha máxima" (que pode ser vista, por exemplo, aqui http://www.studfiles.ru/preview/5175815/page:4 ) .
A lógica aproximada de seu trabalho é a seguinte:
0. A tabela original é considerada o TP transformado atual, o conjunto de linhas de cobertura está vazio;
1. A coluna com menos unidades é destacada na tabela atual. Entre as linhas que contêm unidades nesta coluna, uma com o maior número de unidades é destacada. Esta linha está incluída na cobertura; a tabela atual é reduzida ao excluir todas as colunas nas quais a linha selecionada possui uma unidade.
2. Se não houver colunas riscadas na tabela, a etapa 1 será executada; caso contrário, a cobertura será construída. Nota: Ao calcular o número de unidades em uma linha, as unidades nas colunas não marcadas são levadas em consideração.
Esse algoritmo funciona rápido o suficiente e fornece um resultado próximo do ideal.
Para testar a operação do algoritmo, propõe-se o uso da função de teste TestQuineMcCluskeyRandomPart, que, do conjunto total de termos possíveis, é seleciona aleatoriamente apenas a parte especificada 0 <dPart <= 1 (é um parâmetro da função), para a qual a otimização é realizada. Com o parâmetro dPart <1, um conjunto truncado de termos de entrada será obtido e, com dPart = 1, será obtido um conjunto completo de dados de entrada.
TestQuineMcCluskeyRandomPart (clique para visualizar) 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 da função de teste, são calculados o número de termos na forma normal disjuntiva mínima e o número de erros que o cobrem com o conjunto de termos original.
Concluindo, gostaria de observar que, na prática, essa implementação do algoritmo provou ser um meio eficaz e confiável de minimizar as funções lógicas definidas por dois conjuntos incompletos de termos nos quais a função lógica assume valores TRUE e FALSE, respectivamente. Obviamente, essa implementação também pode ser usada de forma clássica no caso de uma função lógica de entrada completamente definida, quando apenas uma ou outra lista de termos é inserida. Como desvantagem, é necessário verificar na função Skleivanie que não há erros de cobertura para cada termo virtual de toda a lista de termos de origem em cada iteração do algoritmo, o que leva a custos de tempo significativos com um grande número de termos de entrada.