Название Разработка алгоритма программы минимизации логических функций программа с исходниками. Метод Квайна. Минимизация функций алгебры логики. Метод непосредственных преобразований логических функций. Метод Квайна. Реализация минимизации логических функций методом КвайнаМак Класки Хабрахабр. К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических булевых функций ЛФ заданных в виде совершенной дизъюнктивной нормальной формы СДНФ методом КвайнаМак Класки далее просто Мак Класки и проблемы, выявленные при е тестировании. В исследуемом варианте алгоритм Мак Класки реализован на языке C с использованием Generic коллекций библиотеки. NET. Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. Торрент-Тв Все Каналы подробнее. Следовательно, этот набор входных терм, из общего их возможного числа inline2Ninline, где N количество двух классовых категориальных двоичных переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным данном случае истинным выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное false значение. Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак Класки. FiU6RqCWU.HRT4/htmlconvd-HStmH9111x1.jpg' alt='Метод Квайна Программа' title='Метод Квайна Программа' />Формализация производится следующим. Согласно теории метод Мак Класки состоит из двух основных этапов Нахождение всех простых терм ЛФ, используя правило законы склеивания a A B Для запуска оптимизации нужно вызывать один из перегруженных методов Start. В пункте 1 происходит многократный попарный перебор терм с целью выявления возможности их склейки. Два терма склеиваются, если они отличаются друг от друга значениями только лишь в одной из позиций у одного стоит. Склеивающиеся исходные родительские термы исключаются из дальнейшей работы, а вместо их двоих далее на следующей итерации п. Таким образом, двоичный алфавит входных исходных терм внутри алгоритма расширяется до троичного. Первый способ, основанный на 6. NET словаре Dictionarylt UInt. Такое раздвоение обусловлено тем, что первый способ работает несколько быстрее, чем второй, поэтому его использование приоритетнее, но он работает корректно только при количестве входных переменных до 4. Действительно, т. Tree. Func. Term. Промежуточные узлы дерева реализованы с помощью класса Tree. Node. Middle. Каждый из них может ссылаться максимум на три последующих узла в зависимости от того были ли в дерево добавлены соответствующие термы. Все конечные узлы являются экземплярами класса Tree. Node. End, глубина до которых от корня у них всех одинакова и равна количеству входных переменных. Каждый конечный узел также имеет ссылку на другой узел Tree. Node. End, который был добавлен до него, реализуя тем самым однонаправленный связанный список. Такого рода список используется для быстрого перебора всех конечный узлов поискового дерева в процессе их склеивания. Если в п. 1 для терма не находится другого отличающегося от него только в одной позиции терма, т. Reduce. Redundancy. Terms. Отбрасывание избыточных терм в Reduce. Redundancy. Terms осуществляется с помощью алгоритма приближенного решения задачи о покрытии множества подмножествами переменной длины. Покрытие, близкое к кратчайшему дат алгоритм преобразования таблицы покрытий ТП, основанный на методе минимальный столбецмаксимальная строка, который можно посмотреть, например здесь. Приблизительная логика его работы состоит в следующем Исходная таблица считается текущей преобразуемой ТП, множество строк покрытий пусто В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу Если в таблице есть не вычеркнутые столбцы, то выполняется п. Первая процедура позволяет для набора входных переменных количеством N сформировать совокупность терм количеством inline2Ninline, вычислить случайное значение ЛФ для каждого терма и выгрузить в файл только те термы, для которых соответствующее им значение функции было равно TRUE. После этого проводится проверка правильности работы минимизированной формы функции путм вычисления е значения для каждого терма и сравнения с исходным. Test. Quine. Mc. Cluskey. Random нажать для просмотраpublic static void Test. Quine. Mc. Cluskey. Randomstring s. File. Name, int i. Variable. Amount. Если же используется сокращнный неполный набор с количеством Q lt Qпор lt inline2Ninline, то проблема не возникает до той поры, пока размер входного набора данных не перерастт некоторый порог Qпор, критичный для алгоритма. В качестве возможных путей преодоления этой проблемы исследовалась возможность определения Tree. Node. End и Tree. Node. Middle не в виде классов языка C, а в виде структур. Но в связи с принципиальным отличием между классами и структурами, состоящая в том, что нельзя получить ссылку на структуру, этот путь оказался тупиковым вследствие того, что исследуемая реализация в своей работе опирается именно на ссылки к Tree. Node. End и Tree. Node. Middle. Другим направлением преодоления проблемы с памятью было максимальная очистка памяти сборщиком мусора перед каждой итерацией в внутри п. Для этого в код функции Logic. Func. Minimize были добавлены явные вызовы сборщика мусора garbage collector. Выяснилось, что с уборкой мусора время работы значительно меньше, чем без неХотя, казалось бы, на работу сборщика мусора должно тратиться время, что должно было ухудшить результат. Возможное объяснение этого феномена заключается в том, что освобождение памяти сборщиком уменьшает е дефрагментацию в куче, что положительно сказывается на скорости поиска свободных участков при последующем е массовом выделении. Каких либо иных возможностей на преодоление неприятностей с нехваткой памяти я не вижу. В связи с чем возникает вопрос можно ли что то изменить, чтобы добиться стабильной работы алгоритма на полном наборе входных терм с количеством переменных хотя бы до 3. Или это врожднное свойство этого алгоритма, которое не поддатся коррекции Тем не менее, несмотря на возможные проблемы с памятью, предложенная реализация алгоритма Мак Класки в реальных задачах может быть использована в качестве достаточно быстрого и наджного оптимизатора ЛФ, заданных набором терм своих входных переменных, при которых логическая функция принимает истинное значение, когда количество переменных Nlt 1. Q lt lt inline2Ninline.