Artikel ini, sampai batas tertentu, merupakan kelanjutan dari artikel saya tentang meminimalkan fungsi logis dengan metode Quine-Mac'Klaski (
https://habr.com/post/328506 ). Ini dianggap sebagai kasus dengan fungsi logis yang sepenuhnya didefinisikan (walaupun ini tidak secara langsung disebutkan di dalamnya, tetapi hanya tersirat). Pada kenyataannya, kasus seperti itu sangat jarang terjadi ketika jumlah variabel input kecil. Didefinisikan sebagian atau tidak lengkap adalah fungsi logis yang nilainya hanya diberikan untuk bagian Q dari set lengkap P =
set yang mungkin (istilah) dari argumen mereka (variabel) dari nomor
N , yaitu, Q <P. Situasi ini ditemui dalam prakteknya dalam kebanyakan kasus penerapan algoritma untuk mengoptimalkan fungsi logis. Memang, misalnya, jika jumlah variabel input adalah
N = 30, yang merupakan kasus biasa, misalnya, di pasar keuangan, maka volume sampel pelatihan input harus dalam urutan
>
istilah unik yang unik. Array data seperti itu tidak ditemukan di setiap organisasi yang sangat besar, belum lagi individu, yaitu, ini sudah menjadi ranah BigData, penggunaan pusat data, dll.
Oleh karena itu, dalam praktiknya, fungsi logis yang paling sering diminimalkan tidak akan sepenuhnya ditentukan hanya karena kurangnya jumlah akumulasi data yang diperlukan atau karena berbagai alasan objektif lainnya (misalnya, tidak ada cukup ruang untuk menyimpannya). Pertanyaan muncul tentang kemungkinan "pengelakan" dari masalah ini ketika menggunakan suatu algoritma yang bekerja dengan satu set yang lengkap dari istilah fungsi logis, seperti, misalnya, dari artikel saya sebelumnya.
Praktik standar dalam hal ini adalah untuk menentukan set input variabel (istilah) nilai yang tidak lengkap ke yang lengkap sehingga memberikan hasil yang optimal untuk set data yang ada. Tetapi, dalam kasus ini, ada masalah dalam menyebutkan semua varian yang mungkin dari definisi tambahan, jumlah totalnya adalah V =
untuk memilih opsi terbaik untuk definisi tambahan sesuai dengan kriteria yang diberikan. Jelas, untuk nilai Q dan P yang benar-benar digunakan, jumlah opsi yang diurutkan untuk definisi tambahan sangat besar dan pendekatan ini tidak dapat diimplementasikan dalam praktik karena biaya komputasi yang sangat besar.
Dengan demikian, pendekatan yang berbeda diperlukan yang akan menghilangkan kebutuhan untuk menyebutkan berbagai opsi untuk definisi tambahan. Oleh karena itu, perlu untuk memodernisasi algoritma asli, yang awalnya hanya bekerja dengan set input yang terdefinisi penuh, sehingga dapat juga bekerja dengan set terpotong. Ini adalah implementasi dari algoritma yang diusulkan dalam artikel ini, berdasarkan pada fakta bahwa selama proses minimalisasi dua daftar istilah yang tidak lengkap diproses secara bersamaan, di mana fungsi tersebut ditentukan sebagai FALSE (0) dan TRUE (1).
Dari sudut pandang pembelajaran mesin, algoritma Quine-Mac'Klaski mengimplementasikan paradigma pembelajaran dengan guru ketika nilai-nilai output yang sesuai dari fungsi tujuan terlibat dalam proses pembelajaran (dalam hal ini, minimalisasi) secara bersamaan. Biarkan saya mengingatkan Anda bahwa prinsip pengoperasian metode Quine-Mac'Klaski dasar menurut teori terdiri dari dua tahap utama:
- Panggung. Menemukan semua istilah LF sederhana menggunakan aturan perekatan (hukum):
a) (A & B)? (A &! B)? A;
b) (A? B) & (A ?! B)? A;
di mana & adalah operasi AND logis; - operasi logis "ATAU";! - operasi negasi logis "TIDAK". Dari rumus-rumus ini dapat disimpulkan bahwa dua istilah dilem bersama jika mereka berbeda satu sama lain hanya di salah satu posisi variabel. Di posisi di mana kedua istilah berbeda satu sama lain, tanda "*" diletakkan. Dengan demikian, alfabet dalam istilah terpaku dibandingkan dengan aslinya memperluas ke tiga nilai:
• 0 => salah;
• 1 => benar;
• 2 => variabel terpaku (*). - Panggung. Meminimalkan jumlah terpaku-dalam istilah yang diperoleh setelah tahap pertama, sebagai masalah menemukan cakupan optimal dari ketentuan awal dengan kuantitas Q. Artinya, karena masing-masing istilah output hanya mencakup subset tertentu dari istilah awal, maka perlu untuk memilih satu set minimal persyaratan istilah yang diidentifikasi dengan dengan mereka, himpunan bagian panjang yang berbeda dalam agregat sepenuhnya mencakup semua istilah input awal. Pelapisan dalam hal ini berarti bahwa operasi bitwise disjungsi dari istilah output selama istilah input memberikan nilai sebenarnya. Katakanlah istilah keluaran terpaku memiliki bentuk berikut: 10 * 0110 *.
Maka itu mencakup istilah 10101100:
10 * 0110 * & 10101100 = BENAR
tetapi tidak mencakup istilah 00101100:
10 * 0110 * & 00101100 = SALAH
Artinya, istilah input dan output harus bertepatan di mana-mana kecuali untuk posisi di mana ada simbol "*" - di posisi ini variabel istilah input dapat mengambil nilai apa pun, karena dalam posisi ini variabel dikecualikan dari pertimbangan.
Kode implementasi adalah sebagai berikut (klik untuk melihat):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(); } } }
Kelas Quine_McCluskey adalah implementasi dari algoritma ini yang menggunakan kelas dan antarmuka lain: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Untuk memulai optimasi, Anda perlu memanggil salah satu metode Mulai yang kelebihan beban, yang memanggil fungsi LogicFuncMinimize, di mana, pada kenyataannya, algoritma minimisasi diterapkan. Mekanisme minimisasi diterapkan dalam dua versi:
• Menggunakan wadah .NET SortedSet untuk menyimpan dan mencari istilah.
• tanpa menggunakan wadah .NET berdasarkan pohon ternary TreeFuncTerm.
Dalam hal kecepatan, kedua opsi ini kira-kira sama (dengan wadah .NET, mungkin sedikit lebih cepat, tetapi tidak selalu), tetapi kebutuhan untuk mengimplementasikan TreeFuncTerm disebabkan oleh beberapa faktor:
• Opsi pertama, berdasarkan kode hash integer 64-bit dan pencarian dalam kamus .NET SortedSet. Bekerja dengan benar hanya dengan jumlah variabel input hingga 40, dan dengan jumlah yang lebih besar melampaui grid kode hash integer 64-bit, digunakan untuk operasi kontainer. Memang, karena logika ternary digunakan dalam istilah terpaku di dalam algoritma, maka dengan jumlah variabel input sama dengan 41, nilai maksimum dari kode hash
sudah melebihi nilai maksimum
-1, yang dapat ditulis ke variabel 64 bit. Dengan lebih banyak variabel, opsi digunakan berdasarkan pohon pencarian ternary penulis TreeFuncTerm.
• Diperlukan untuk memeriksa operasi implementasi pada wadah .NET dengan implementasi lain yang independen darinya, bebas dari itu.
• Anda hanya perlu opsi yang bebas dari wadah .NET, yang dapat dengan mudah diimplementasikan pada platform di mana tidak ada platform .NET (misalnya, dalam mikrokontroler, FPGA, dll.).
Pengoperasian pohon pencarian TreeFuncTerm didasarkan pada konfigurasi tautan ke kelas TreeNodeMiddle dan TreeNodeEnd, yang merupakan implementasi dari antarmuka TreeNodeBase. Kelas TreeNodeMiddle adalah simpul tengah dari pohon, dan kelas TreeNodeEnd adalah ujung daun pohon. Menggunakan fungsi EnumerationInit () dan EnumerationNextNode (), mekanisme non-rekursif untuk enumerasi semua daun daun TreeNodeEnd diimplementasikan di pohon. Fungsi EnumerationInit () menginisialisasi enumerasi dan mengembalikan daun pertama di pohon. Fungsi EnumerationNextNode () mengembalikan daun pohon berikutnya atau NULL jika tidak ada lagi daun untuk pemilihan. Selain itu, struktur internal tambahan EnumerationTerm, yang mencerminkan posisi pencarian "kursor" di dalam pohon, juga merupakan kode istilah dari lembar yang ditemukan dalam logika ternary {0,1,2}. Perlu dicatat bahwa urutan pemilihan daun dari pohon tidak sesuai dengan urutan penambahannya.
Algoritma untuk tujuan fungsional dapat dibagi menjadi tiga tahap.
- Persiapan. Untuk memecahkan masalah di atas dalam menghilangkan enumerasi opsi untuk definisi tambahan dalam implementasi yang dipertimbangkan, fungsi LogicFuncMinimize menerima dua dataset awal PositivTerms dan NegativTerms, di mana fungsi yang dioptimalkan masing-masing menerima nilai true (TRUE, 1) dan false (FALSE, 0). Pertama-tama, daftar ini diperiksa untuk konsistensi dari sumber data. Adalah perlu bahwa setiap set data dijamin hanya berisi istilah unik yang hanya ada di salah satu daftar. Untuk menjamin ini, setiap istilah input unik dipindai dan jumlah entri di setiap daftar sumber ditemukan. Jika istilah tersebut muncul di kedua daftar, maka hanya tinggal dalam daftar di mana ia muncul lebih banyak, dan dihapus dari yang lain. Jika istilah tersebut muncul di masing-masing daftar dengan frekuensi yang sama, maka dihapus dari kedua daftar, yang memastikan keunikan.
- Ikatan. Selanjutnya, siklus berulang untuk menempelkan istilah input dilakukan. Pada setiap iterasi, dalam istilah terpaku, satu tanda * dari posisi terpaku ditambahkan. Oleh karena itu, jumlah iterasi tidak boleh lebih besar dari jumlah variabel N. Berbeda dengan implementasi sebelumnya, fungsi Skleivanie untuk menempelkan istilah input memiliki kemampuan untuk merekatkan tidak hanya dengan istilah dari daftar, tetapi juga dengan tidak adanya istilah dengan satu perbedaan juga dengan apa yang disebut istilah "virtual". Yang dimaksud dengan istilah "virtual" adalah istilah yang didefinisikan secara artifisial yang tidak ditemukan dalam daftar istilah dari set level saat ini. Tetapi menempel hanya mungkin jika istilah "virtual" tidak mencakup satu istilah dari set awal dari daftar yang berlawanan.
Fungsi Skleivanie dipanggil untuk memproses daftar pada setiap iterasi dua kali sehingga dalam panggilan pertama, makna menggunakan daftar PositivTerms dan NegativTerms bertepatan dengan konten aktualnya, dan pada panggilan kedua, daftar PositivTerms dan NegativTerms dipertukarkan dalam hal penggunaan, mis. Dianggap bahwa Daftar PositivTerms berisi istilah negatif, dan daftar NegativTerms berisi istilah positif:
Skleivanie (X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, ...);
Skleivanie (X1NegativTree, ..., X1PositivTree, ..., null, ...);
Dengan demikian, pengelompokan saling bergantung secara simultan dari ketentuan dua daftar terjadi.
Jika untuk istilah tidak ada istilah lain yang berbeda dari itu hanya dalam satu posisi, baik nyata maupun virtual, yaitu, istilah tersebut tidak menempel bersama siapa pun, maka dianggap sebagai salah satu hasil langkah 1 dari algoritma, itu dikecualikan dari pekerjaan lebih lanjut di dalamnya dan pergi ke input tahap 2 dari algoritma yang diterapkan dalam prosedur ReduceRedundancyTerms. Istilah-istilah yang tidak dilem dikirim ke output algoritma hanya pada panggilan itu ke fungsi Skleivanie, yang artinya menggunakan daftar PositivTerms dan NegativTerms bertepatan dengan pengisian aktualnya, yaitu, pada panggilan pertama. - Singkatan. Istilah terpaku yang terputus-putus dibuang di ReduceRedundancyTerms menggunakan algoritme untuk perkiraan penyelesaian masalah yang meliputi set asli dengan subset panjang variabel. Cakupan, yang dekat dengan yang terpendek, disediakan oleh algoritma untuk mengonversi tabel cakupan (TP), berdasarkan metode "kolom minimum - baris maksimum" (yang dapat dilihat, misalnya, di sini http://www.studfiles.ru/preview/5175815/page:4 ) .
Perkiraan logika karyanya adalah sebagai berikut:
0. Tabel asli dianggap sebagai TP yang diubah saat ini, rangkaian garis cakupan kosong;
1. Kolom dengan unit paling sedikit disorot dalam tabel saat ini. Di antara baris yang berisi unit dalam kolom ini, satu dengan jumlah unit terbesar disorot. Baris ini termasuk dalam cakupan, tabel saat ini dikurangi dengan menghapus semua kolom di mana baris yang dipilih memiliki unit.
2. Jika tidak ada kolom dicoret dalam tabel, maka langkah 1 dilakukan, jika tidak, cakupan dibangun. Catatan: Saat menghitung jumlah unit dalam satu baris, unit dalam kolom yang tidak ditandai diperhitungkan.
Algoritma ini bekerja cukup cepat dan memberikan hasil mendekati optimal.
Untuk menguji operasi algoritme, diusulkan untuk menggunakan fungsi tes TestQuineMcCluskeyRandomPart, yang, dari total kumpulan istilah yang mungkin, adalah secara acak memilih hanya bagian yang diberikan 0 <dPart <= 1 (merupakan parameter fungsi), yang untuknya optimasi dilakukan. Dengan parameter dPart <1, satu set istilah input terpotong akan diperoleh, dan dengan dPart = 1, satu set data input yang lengkap akan diperoleh.
TestQuineMcCluskeyRandomPart (klik untuk melihat) 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(); }
Sebagai hasil dari fungsi pengujian, jumlah istilah dalam bentuk normal disjungtif minimum dan jumlah kesalahan yang menutupinya dengan kumpulan istilah asli dihitung.
Sebagai kesimpulan, saya ingin mencatat bahwa dalam praktiknya implementasi algoritma ini telah terbukti menjadi cara yang efektif dan dapat diandalkan untuk meminimalkan fungsi logis yang didefinisikan oleh dua set istilah yang tidak lengkap di mana fungsi logis mengambil nilai TRUE dan FALSE, masing-masing. Tentu saja, implementasi ini juga dapat digunakan dalam bentuk klasik dalam kasus fungsi logis input yang sepenuhnya didefinisikan, ketika hanya satu atau beberapa daftar istilah yang dimasukkan. Sebagai kelemahan, perlu untuk memeriksa dalam fungsi Skleivanie bahwa tidak ada kesalahan cakupan untuk setiap istilah virtual dari seluruh daftar istilah sumber pada setiap iterasi algoritma, yang mengarah ke biaya waktu yang signifikan dengan sejumlah besar istilah input.