Данная статья является, в некоторой степени, продолжением моей статьи по минимизации логических функций методом Квайна-Мак’Класки (https://habr.com/post/328506). В ней рассматривался случай с полностью определёнными логическими функциями (хотя этого в ней прямо не упоминалось, а только подразумевалось). В реальности такой случай встречается достаточно редко, когда количество входных переменных мало. Частично или не полностью определенными называются логические функции, значения которых заданы лишь для части Q из полного множества P= возможных наборов (термов) их аргументов (переменных) количеством N, т. е. Q < P. Такая ситуация встречается на практике в большинстве случаев применений алгоритмов оптимизации логических функций. Действительно, например, если число входных переменных N=30, что является заурядным случаем, например на финансовых рынках, то объём входной обучающей выборки должен составлять порядка > элементарных уникальных термов. Такой массив данных встречается не в каждой даже очень крупной организации, не говоря уже о частных лицах, т. е. это уже сфера BigData, использования ЦОД-ов и т. д.
Поэтому на практике чаще всего минимизируемые логические функции будут определены не полностью просто в силу отсутствия необходимого количества накопленных данных или в силу разных других объективных причин (например, не хватает места для их хранения). Возникает вопрос о возможности «обхода» этой неприятности при использовании алгоритма, работающего с полностью определённым набором терм логической функции, таким как, например, из предыдущей моей статьи.
Стандартной практикой в этом случае является доопределение неполного входного набора значений переменных (термов) до полного таким образом, чтобы оно давало оптимальный результат для имеющегося набора данных. Но, в этом случае, возникает проблема в переборе всех возможных вариантов доопределений, общее количество которых составляет V=, чтобы выбрать оптимальный вариант доопределения в соответствии с заданным критерием. Очевидно, что для реально используемых значений Q и P количество перебираемых вариантов доопределений астрономически велико и такой подход не реализуем на практике в силу грандиозности вычислительных затрат.
Таким образом, нужен другой подход, который бы устранил необходимость перебора различных вариантов доопределений. Следовательно, необходимо так модернизировать исходный алгоритм, работающий изначально только с полностью определённым входным набором, чтобы он мог работать также и с усеченным набором. Именно такая реализация алгоритма и предлагается в данной статье, основанная на том, что в процессе минимизации обрабатываются одновременно два неполных списка терм, на которых функция задана как FALSE (0) и TRUE (1).
С точки зрения машинного обучения алгоритм Квайна-Мак’Класки реализует парадигму обучения с учителем, когда одновременно с входными данными в процессе обучения (в данном случае минимизации) участвует соответствующие им выходные значения целевой функции. Напомню, что принцип работы базового метода Квайна-Мак’Класки согласно теории состоит из двух основных этапов:
Класс Quine_McCluskey является реализацией этого алгоритма, который использует другие классы и интерфейсы: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Для запуска оптимизации нужно вызывать один из перегруженных методов Start, который вызывает функцию LogicFuncMinimize, где реализован, собственно, алгоритм минимизации. Механизм минимизации реализован в двух вариантах:
• с использованием контейнера .NET SortedSet для хранения и поиска термов.
• без использования контейнеров .NET на основе троичного дерева TreeFuncTerm.
По скорости эти два варианта примерно равны (с контейнерами .NET, возможно, чуть быстрее, но далеко не всегда), но необходимость реализации TreeFuncTerm обусловлен несколькими факторами:
• Первый вариант, основанный на 64-х битных целочисленных хэш-кодах и поиске в .NET словаре SortedSet, работает корректно только при количестве входных переменных в термах до 40, а при большем их количестве выходит за 64 битную разрядную сетку целочисленного хэш-кода, используемого для работы контейнера. Действительно, т. к. в склеенных термах внутри алгоритма применяется троичная логика, то при количестве входных переменных равном 41 максимальное значение хэш-кода уже превышает максимальное значение -1, которое можно записать в 64 битную переменную. При большем количестве переменных используется вариант, основанный на авторском троичном поисковом дереве TreeFuncTerm.
• Нужно проверять работу реализации на контейнерах .NET другой независимой от неё реализацией свободной от них.
• Просто нужен вариант, свободный от контейнеров .NET, который можно было бы легко реализовать на платформах, где нет платформы .NET (например в микроконтроллерах, ПЛИС и т. п.).
Работа поискового дерева TreeFuncTerm основана на конфигурации ссылок классов TreeNodeMiddle и TreeNodeEnd, являющихся реализациями интерфейса TreeNodeBase. Класс TreeNodeMiddle является промежуточным узлом дерева, а класс TreeNodeEnd – оконечным листом дерева. В дереве с помощью функций EnumerationInit() и EnumerationNextNode() реализован нерекурсивный механизм перебора всех конечных листьев TreeNodeEnd. Функция EnumerationInit() инициализирует перебор и возвращает первый попавшийся лист дерева. Функция EnumerationNextNode() возвращает следующий лист дерева или NULL, если листьев для выборки больше нет. При этом вспомогательная внутренняя структура EnumerationTerm, которая отражает положение поискового «курсора» внутри дерева, является также кодом терма найденного листа в троичной логике {0,1,2}. Следует заметить, что порядок выборки листьев из дерева не совпадает с порядком добавления их в него.
Алгоритм по функциональному назначению можно разбить на три этапа.
В результате работы тестовой функции рассчитывается количество термов в минимальной дизъюнктивной нормальной форме и количество ошибок покрытия ею исходного набора терм.
В заключение хотелось отметить, что на практике эта реализация алгоритма показала себя эффективным и надёжным средством минимизации логических функций, заданных двумя неполными наборами терм, на которых логическая функция принимает соответственно TRUE и FALSE значения. Конечно, также эту реализацию можно использовать в классическом виде в случае полностью определённой входной логической функции, когда на вход подаётся только один тот или иной список термов. В качестве недостатка можно отметить необходимость проверки в функции Skleivanie отсутствия ошибок покрытия для каждого виртуального терма всего списка исходных термов на каждой итерации алгоритма, что приводит к существенным временным затратам при большом количестве входных термов.
Поэтому на практике чаще всего минимизируемые логические функции будут определены не полностью просто в силу отсутствия необходимого количества накопленных данных или в силу разных других объективных причин (например, не хватает места для их хранения). Возникает вопрос о возможности «обхода» этой неприятности при использовании алгоритма, работающего с полностью определённым набором терм логической функции, таким как, например, из предыдущей моей статьи.
Стандартной практикой в этом случае является доопределение неполного входного набора значений переменных (термов) до полного таким образом, чтобы оно давало оптимальный результат для имеющегося набора данных. Но, в этом случае, возникает проблема в переборе всех возможных вариантов доопределений, общее количество которых составляет V=, чтобы выбрать оптимальный вариант доопределения в соответствии с заданным критерием. Очевидно, что для реально используемых значений Q и P количество перебираемых вариантов доопределений астрономически велико и такой подход не реализуем на практике в силу грандиозности вычислительных затрат.
Таким образом, нужен другой подход, который бы устранил необходимость перебора различных вариантов доопределений. Следовательно, необходимо так модернизировать исходный алгоритм, работающий изначально только с полностью определённым входным набором, чтобы он мог работать также и с усеченным набором. Именно такая реализация алгоритма и предлагается в данной статье, основанная на том, что в процессе минимизации обрабатываются одновременно два неполных списка терм, на которых функция задана как FALSE (0) и TRUE (1).
С точки зрения машинного обучения алгоритм Квайна-Мак’Класки реализует парадигму обучения с учителем, когда одновременно с входными данными в процессе обучения (в данном случае минимизации) участвует соответствующие им выходные значения целевой функции. Напомню, что принцип работы базового метода Квайна-Мак’Класки согласно теории состоит из двух основных этапов:
- Этап. Нахождение всех простых терм ЛФ, используя правила (законы) склеивания:
a) (A & B)? (A & !B)? A;
b) (A? B) & (A? !B)? A;
где & — операция логического «И»;? — операция логического «ИЛИ»;! – операция логического отрицания «НЕ». Из этих формул следует, что две термы склеиваются, если они отличаются друг от друга только в одной из позиций переменных. В позиции, где две термы отличаются друг от друга ставится знак «*». Таким образом, алфавит в склеенных термах по сравнению с исходным расширяется до трёх значений:
• 0 => значение false;
• 1 => значение true;
• 2 => склеенная переменная (*). - Этап. Минимизация количества полученного после первого этапа множества склеенных терм, как задача нахождения оптимального покрытия ими исходного множества терм количеством Q. Т. е., так как каждый выходной терм покрывает только определённое подмножество исходных терм, необходимо выбрать такой минимальный набор выходных термов, чтобы отождествлённые с ними подмножества разной длины в совокупности полностью покрывали все исходные входные термы. Под покрытием в данном случае подразумевается, что побитовая операция дизъюнкции выходного терма над входным давала истинное значение. Допустим, выходной склеенный терм имеет следующий вид: 10*0110*.
Тогда он покрывает терм 10101100:
10*0110* & 10101100 = TRUE
но не покрывает терм 00101100:
10*0110* & 00101100 = FALSE
Т. е. входной терм и выходной должны совпадать везде за исключением позиций, где есть символ «*» – в такой позиции переменная входного терма может принимать любое значение, т.к. в этой позиции переменная исключается из рассмотрения.
Код реализации следующий (нажать для просмотра):
using System;
using System.Collections.Generic;
using System.Linq;
/// <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 virtual bool Calculate(char[] X)
{
return Calculate(X.Select(p => p != '0').ToArray());
}
//Вычисление значения функции
public virtual bool Calculate(byte[] X)
{
return Calculate(X.Select(p => p != 0).ToArray());
}
}
/// <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(bool[] X)
{
bool bResult = false;
foreach (byte[] term in Terms)
{
bool TermVal = true;
for (int i = 0; i < term.Length; i++)
{
if (term[i] == cStarSymb) continue;
TermVal &= (term[i] != 0 ? X[i] : !X[i]);
}
bResult |= TermVal;
}
return bResult;
}
}
/// <summary>
/// Конъюнктивная нормальная форма
/// </summary>
public class Knf : LogicFunction
{
public override bool Calculate(bool[] X)
{
bool bResult = true;
foreach (byte[] term in Terms)
{
bool TermVal = false;
for (int i = 0; i < term.Length; i++)
{
if (term[i] == cStarSymb) continue;
TermVal |= (term[i] != 0 ? X[i] : !X[i]);
}
bResult &= TermVal;
}
return bResult;
}
}
/// <summary>
/// Дерево термов
/// </summary>
public class TreeFuncTerm
{
//Корень
private readonly TreeNodeMiddle rootNode = new TreeNodeMiddle();
//Ранг (глубина) дерева
private int _rang = 0;
public int Rang
{
get { return _rang; }
}
//Для работы перечисления узлов
private int enumerationPos = 0;
private TreeNodeMiddle[] 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.Clear();
}
//Инициализировать процесс перебора конечных узлов дерева
public TreeNodeEnd EnumerationInit()
{
enumerationPos = 0;
enumerationTerm = new byte[_rang];
enumerationTerm[0] = 0;
enumerationBuf = new TreeNodeMiddle[_rang];
enumerationBuf[0] = rootNode;
//Вернуть первый конечный узел
return EnumerationNextNode();
}
//Получить следующий конечный узел дерева
public TreeNodeEnd EnumerationNextNode()
{
int iIsNext = (enumerationPos > 0 ? 1 : 0);
TreeNodeEnd pRetTreeNode = null;
while ((pRetTreeNode == null) && (enumerationPos >= 0))
{
TreeNodeBase[] pCurrNodes = enumerationBuf[enumerationPos].Childs;
TreeNodeBase 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 TreeNodeMiddle)
{
//Переход на следующий уровень
enumerationPos++;
enumerationBuf[enumerationPos] = (TreeNodeMiddle)pNextNode;
enumerationTerm[enumerationPos] = 0;
iIsNext = 0;
}
else //if (pNextNode is TreeNodeEnd)
{
//Найден конечный узел
pRetTreeNode = (TreeNodeEnd)pNextNode;
}
}
}
return pRetTreeNode;
}
//Добавление в дерево нового терма
public TreeNodeEnd AddTerm(byte[] term)
{
_rang = Math.Max(_rang, term.Length);
TreeNodeBase pCurrNode = rootNode;
for (int j = 0; j < term.Length; j++)
{
TreeNodeBase item = ((TreeNodeMiddle)pCurrNode).Childs[term[j]];
if (item == null)
{
if (j + 1 < term.Length)
{
item = new TreeNodeMiddle();
}
else
{
item = new TreeNodeEnd();
_count++;
}
((TreeNodeMiddle)pCurrNode).Childs[term[j]] = item;
}
pCurrNode = item;
}
return (TreeNodeEnd)pCurrNode;
}
//Удаление из контейнера конечного узла последовательности
public TreeNodeEnd Remove(byte[] term)
{
TreeNodeEnd pRemovedNode = null;
TreeNodeMiddle pCurrNode = rootNode;
foreach (byte cSymb in term)
{
TreeNodeBase pNextNode = pCurrNode.Childs[cSymb];
if (pNextNode == null) break;
if (pNextNode is TreeNodeMiddle)
{
pCurrNode = (TreeNodeMiddle)pNextNode;
}
else
{
//Сохраняется возвращаемая ссылка на удаляемый узел
pRemovedNode = (TreeNodeEnd)pNextNode;
//Стираетсяя ссылка на конечный узел
pCurrNode.Childs[cSymb] = null;
//Уменьшается кол-во узлов
_count--;
//Узел удалён - выход
break;
}
}
return pRemovedNode;
}
//Проверка нахождения последовательности в контейнере
public TreeNodeEnd IsContains(byte[] term)
{
TreeNodeBase pCurrNode = rootNode;
foreach (byte cSymb in term)
{
pCurrNode = ((TreeNodeMiddle)pCurrNode).Childs[cSymb];
if (pCurrNode == null) break;
}
return ((pCurrNode != null) && (pCurrNode is TreeNodeEnd) ? (TreeNodeEnd)pCurrNode : null);
}
//Поиск последовательностей с одним отличием от заданной не рекурсивным способом
public int SearchDiff1(byte[] term, TreeNodeBase[] pOneDiffNodesList)
{
int iOneDiffNodesListCount = 0;
TreeNodeBase pCurrNode = rootNode;
for (int iPos = 0; iPos < term.Length; iPos++)
{
pOneDiffNodesList[iPos] = null;
byte cSymbol = term[iPos];
if (pCurrNode != null)
{
if (cSymbol != LogicFunction.cStarSymb)
{
TreeNodeBase item = ((TreeNodeMiddle)pCurrNode).Childs[1 - cSymbol];
if (item != null)
{
//Добавление в массив отобранных терм
pOneDiffNodesList[iPos] = item;
iOneDiffNodesListCount++;
}
}
pCurrNode = ((TreeNodeMiddle)pCurrNode).Childs[cSymbol];
}
else if (iOneDiffNodesListCount == 0)
{
//Массив отобранных терм пуст и нет возможности его заполнения на следующих итерациях
for (int i = iPos + 1; i < term.Length; i++) pOneDiffNodesList[i] = null;
break;
}
//Проверяются последовательности, отобранные на предыдущих позициях,
//на единственность отличия от заданной
for (int iKey = 0; iKey < iPos; iKey++)
{
TreeNodeBase item = pOneDiffNodesList[iKey];
if (item == null) continue;
item = ((TreeNodeMiddle)item).Childs[cSymbol];
if (item == null)
{
//Удаление из массива отобранных терм
pOneDiffNodesList[iKey] = null;
iOneDiffNodesListCount--;
}
else
{
pOneDiffNodesList[iKey] = item;
}
}
}
return iOneDiffNodesListCount;
}
}
/// <summary>
/// Базовый интерфейс узла дерева термов
/// </summary>
public interface TreeNodeBase
{
//Очистка выделенных ресурсов
void Clear();
}
/// <summary>
/// Конечный узел дерева термов
/// </summary>
public class TreeNodeEnd : TreeNodeBase
{
//Очистка выделенных ресурсов
public void Clear() { }
}
/// <summary>
/// Промежуточный узел дерева термов
/// </summary>
public class TreeNodeMiddle : TreeNodeBase
{
//Дочерние узлы
public readonly TreeNodeBase[] Childs = new TreeNodeBase[3];
//Очистка выделенных ресурсов
public void Clear()
{
for (int i = 0; i < 3; i++)
{
if ((Childs[i] != null) && (Childs[i] is TreeNodeMiddle)) ((TreeNodeMiddle)Childs[i]).Clear();
Childs[i] = null;
}
}
}
/// <summary>
/// Минимизация логической функции методом Квайна---Мак-Класки
/// </summary>
public class Quine_McCluskey
{
private readonly Dnf _result = new Dnf();
public Dnf Result
{
get { return _result; }
}
//Склеивание строк с одним различием
private static void Skleivanie(TreeFuncTerm X1Tree, TreeFuncTerm X2Tree, LinkedList<byte[]> NegTerms,
Dictionary<int, LinkedList<byte[]>> OutResult, TreeFuncTerm NegativTree, int iLevel)
{
LinkedList<byte[]> OutR = new LinkedList<byte[]>();
if (OutResult != null) OutResult.Add(iLevel, OutR);
bool IsVirtSkleivOn = ((NegativTree != null) && (NegativTree.Count != 0));
TreeNodeEnd x1 = X1Tree.EnumerationInit();
TreeNodeBase[] FindTerms = new TreeNodeBase[x1 != null ? X1Tree.Rang : 1];
TreeNodeBase[] FindNegTerms = new TreeNodeBase[x1 != null ? X1Tree.Rang : 1];
TreeNodeBase[] FindVirtTerms = new TreeNodeBase[x1 != null ? X1Tree.Rang : 1];
while (x1 != null)
{
bool bIsSkleiv = false;
byte[] pCurrTerm = X1Tree.EnumerationTerm;
X1Tree.SearchDiff1(pCurrTerm, FindTerms);
if (IsVirtSkleivOn) NegativTree.SearchDiff1(pCurrTerm, FindNegTerms);
for (int iPos = 0; iPos < pCurrTerm.Length; iPos++)
{
byte cSymbSav = pCurrTerm[iPos];
if (cSymbSav == LogicFunction.cStarSymb) continue;
//Склеивание двух термов с одним различием или
//склеивание с виртуальной термой, которой нет в NegativTree
if (FindTerms[iPos] != null)
{
bIsSkleiv = true;
if (cSymbSav == 0)
{
pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
X2Tree.AddTerm(pCurrTerm);
pCurrTerm[iPos] = cSymbSav;
}
}
else if (IsVirtSkleivOn && (FindNegTerms[iPos] == null))
{
pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
bool bIsNotCanAdd = false;
foreach (byte[] NegTerm in NegTerms)
{
if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break;
}
if (!bIsNotCanAdd)
{
bIsSkleiv = true;
X2Tree.AddTerm(pCurrTerm);
}
pCurrTerm[iPos] = cSymbSav;
}
}
//Добавление на выход тех термов, которые ни с кем не склеились
if (!bIsSkleiv) OutR.AddLast(pCurrTerm.ToArray());
//Переход к следующему терму
x1 = X1Tree.EnumerationNextNode();
}
}
//Возвращает уникальный код для терма
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 = new byte[iTermLength];
int iCounter = 0;
while (iCode != 0)
{
pTerm[iCounter++] = (byte)(iCode % 3);
iCode /= 3;
}
return pTerm;
}
//Склеивание строк с одним различием
private static void Skleivanie(SortedSet<UInt64> X1Tree, SortedSet<UInt64> X2Tree, LinkedList<byte[]> NegTerms,
Dictionary<int, LinkedList<byte[]>> OutResult, SortedSet<UInt64> NegativTree, int iLevel,
int iTermLength)
{
LinkedList<byte[]> OutR = new LinkedList<byte[]>();
if (OutResult != null) OutResult.Add(iLevel, OutR);
bool IsVirtSkleivOn = ((NegativTree != null) && (NegativTree.Count != 0));
foreach (UInt64 x1 in X1Tree)
{
byte[] pCurrTerm = (IsVirtSkleivOn ? GetTermByCode(x1, iTermLength) : null);
bool bIsSkleiv = false;
UInt64 iMultip = 1;
for (int iPos = 0; iPos < iTermLength; iPos++)
{
byte cSymbSav = (pCurrTerm != null ? pCurrTerm[iPos] : (byte)((x1 / iMultip) % 3));
if (cSymbSav != LogicFunction.cStarSymb)
{
UInt64 iCode = (cSymbSav == 0 ? x1 + iMultip : x1 - iMultip);
//Склеивание двух термов с одним различием или
//склеивание с виртуальной термой, которой нет в NegativTree
if (X1Tree.Contains(iCode))
{
bIsSkleiv = true;
if (cSymbSav == 0)
{
X2Tree.Add(x1 + (byte)(LogicFunction.cStarSymb - cSymbSav) * iMultip);
}
}
else if (IsVirtSkleivOn && !NegativTree.Contains(iCode))
{
bool bIsNotCanAdd = false;
pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
foreach (byte[] NegTerm in NegTerms)
{
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(pCurrTerm != null ? pCurrTerm : GetTermByCode(x1, iTermLength));
}
}
//Удаление дубликатов термов из входного списка
//В выходной словарь добавляются только уникальные термы
private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, SortedSet<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, LinkedList<byte[]> NegTerms, Dictionary<int, LinkedList<byte[]>> OutputTerms, ICollection<byte[]> ResultTerms)
{
//Подготовка результирующего контейнера
ResultTerms.Clear();
//Контейнер первичных входных термов, образовавшие текущие отобранные выходные термы
HashSet<byte[]> pNumbersForAdd = new HashSet<byte[]>();
//Контейнер для соответствия первичных входных терм к тому списку выходных, которые их покрывают
Dictionary<byte[], HashSet<byte[]>> Numbers2Terms = new Dictionary<byte[], HashSet<byte[]>>();
//Контейнер для соответствия конечного терма к списку первичных термов, которые его образовали
Dictionary<byte[], HashSet<byte[]>> Terms2Numbers = new Dictionary<byte[], HashSet<byte[]>>();
//Формирование распределения по уровню
foreach (int iLevel in OutputTerms.Keys.OrderByDescending(p => p).AsEnumerable())
{
//Сбор статистики об покрытии выходными термами входных
foreach (byte[] term in OutputTerms[iLevel])
{
//Контейнер входных термов, которые покрывает данный выходной терм term
HashSet<byte[]> InTermsCont = new HashSet<byte[]>();
//Цикл по всем входным термам
foreach (byte[] InpTerm in InpTerms)
{
if (Dnf.Calculate(InpTerm, term)) InTermsCont.Add(InpTerm);
}
//Цикл по всем негативным термам (если они есть)
if (NegTerms != null)
{
foreach (byte[] NegTerm in NegTerms)
{
if (!Dnf.Calculate(NegTerm, term)) InTermsCont.Add(NegTerm);
}
}
Terms2Numbers.Add(term, InTermsCont);
}
//Для определения того, что терм имеет те же покрываемые входные термы как предыдущий
int iTerms2NumbersCountPrev = 0;
foreach (byte[] term in OutputTerms[iLevel].OrderByDescending(p => Terms2Numbers[p].Count))
{
//Контейнер входных термов, которые покрывает данный выходной терм term
HashSet<byte[]> InTermsCont = Terms2Numbers[term];
int iIntersectNumbers = pNumbersForAdd.Intersect(InTermsCont).Count();
if ((iIntersectNumbers < InTermsCont.Count) || (iTerms2NumbersCountPrev == InTermsCont.Count))
{
pNumbersForAdd.UnionWith(InTermsCont);
iTerms2NumbersCountPrev = InTermsCont.Count;
foreach (byte[] pSrcNode in InTermsCont)
{
if (!Numbers2Terms.ContainsKey(pSrcNode)) Numbers2Terms.Add(pSrcNode, new HashSet<byte[]>());
Numbers2Terms[pSrcNode].Add(term);
}
}
}
}
//Перебор всех входных термов, отсортированных по кол-ву покрывавших их выходных
while (pNumbersForAdd.Count > 0)
{
byte[] term = Numbers2Terms[pNumbersForAdd.OrderBy(p => Numbers2Terms[p].Count).First()].OrderByDescending(q => pNumbersForAdd.Intersect(Terms2Numbers[q]).Count()).First();
ResultTerms.Add(term);
pNumbersForAdd.ExceptWith(Terms2Numbers[term]);
}
}
//Нахождение минимальной логической функции
public static void LogicFuncMinimize(IEnumerable<byte[]> PositivTerms, IEnumerable<byte[]> NegativTerms, ICollection<byte[]> OutR)
{
int iTotalLevels = (PositivTerms.Count() > 0 ? PositivTerms.First().Length : (NegativTerms != null && NegativTerms.Count() > 0 ? NegativTerms.First().Length : 0));
Dictionary<int, LinkedList<byte[]>> SkleivTerms = new Dictionary<int, LinkedList<byte[]>>(iTotalLevels);
LinkedList<byte[]> InpTerms = new LinkedList<byte[]>();
LinkedList<byte[]> NegTerms = new LinkedList<byte[]>();
if (iTotalLevels < 40)
{
SortedSet<UInt64> X1PositivTree = new SortedSet<UInt64>();
DeleteDublicatingTerms(PositivTerms, X1PositivTree);
SortedSet<UInt64> X1NegativTree = null;
if (NegativTerms != null)
{
X1NegativTree = new SortedSet<UInt64>();
DeleteDublicatingTerms(NegativTerms, X1NegativTree);
//Проверка наличия и удаление одинаковых данных в последовательностях
UInt64[] pNumbList = X1PositivTree.Intersect(X1NegativTree).ToArray();
foreach(UInt64 iNumb in pNumbList)
{
//Подсчитывается кол-во входных термов в 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)
{
NegTerms.AddLast(GetTermByCode(code, iTotalLevels));
}
}
//Формирование списка входных термов для этапа проверки покрытия выходных термов
foreach (UInt64 code in X1PositivTree)
{
InpTerms.AddLast(GetTermByCode(code, iTotalLevels));
}
int iLevelCounter = 0;
//Повтор до тех пор пока будут оставаться термы
while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels))
{
SortedSet<UInt64> X2Tree = new SortedSet<UInt64>();
Skleivanie(X1PositivTree, X2Tree, NegTerms, SkleivTerms, X1NegativTree, iLevelCounter, iTotalLevels);
if ((X1NegativTree != null) && (X1NegativTree.Count != 0))
{
SortedSet<UInt64> X2NegativTree = new SortedSet<UInt64>();
Skleivanie(X1NegativTree, X2NegativTree, InpTerms, null, X1PositivTree, iLevelCounter, iTotalLevels);
//Очистка поискового словаря
X1NegativTree.Clear();
X1NegativTree = X2NegativTree;
}
//Очистка поискового словаря
X1PositivTree.Clear();
X1PositivTree = X2Tree;
iLevelCounter++;
GC.Collect();
}
}
else
{
TreeFuncTerm X1PositivTree = new TreeFuncTerm();
DeleteDublicatingTerms(PositivTerms, X1PositivTree);
TreeFuncTerm X1NegativTree = null;
if (NegativTerms != null)
{
X1NegativTree = new TreeFuncTerm();
DeleteDublicatingTerms(NegativTerms, X1NegativTree);
//Проверка наличия и удаление одинаковых данных в обеих последовательностях
TreeNodeEnd x1 = X1PositivTree.EnumerationInit();
while (x1 != null)
{
if (X1NegativTree.IsContains(X1PositivTree.EnumerationTerm) != null)
{
//Подсчитывается кол-во входных термов в 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);
}
}
x1 = X1PositivTree.EnumerationNextNode();
}
//Формирование списка входных негативных термов для этапа проверки покрытия выходных термов
x1 = X1NegativTree.EnumerationInit();
while (x1 != null)
{
NegTerms.AddLast(X1NegativTree.EnumerationTerm.ToArray());
x1 = X1NegativTree.EnumerationNextNode();
}
}
//Формирование списка входных термов для этапа проверки покрытия выходных термов
TreeNodeEnd X1Term = X1PositivTree.EnumerationInit();
while (X1Term != null)
{
InpTerms.AddLast(X1PositivTree.EnumerationTerm.ToArray());
X1Term = X1PositivTree.EnumerationNextNode();
}
int iLevelCounter = 0;
//Повтор до тех пор пока будут оставаться термы
while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels))
{
TreeFuncTerm X2Tree = new TreeFuncTerm();
Skleivanie(X1PositivTree, X2Tree, NegTerms, SkleivTerms, X1NegativTree, iLevelCounter);
if ((X1NegativTree != null) && (X1NegativTree.Count != 0))
{
TreeFuncTerm X2NegativTree = new TreeFuncTerm();
Skleivanie(X1NegativTree, X2NegativTree, InpTerms, null, X1PositivTree, iLevelCounter);
//Очистка поискового дерева
X1NegativTree.Clear();
X1NegativTree = X2NegativTree;
}
//Очистка поискового дерева
X1PositivTree.Clear();
X1PositivTree = X2Tree;
iLevelCounter++;
GC.Collect();
}
}
//Выбор оптимального набора терм
ReduceRedundancyTerms(InpTerms, NegTerms, SkleivTerms, OutR);
}
//Запуск метода
public void Start(IEnumerable<byte[]> TermsInput)
{
LogicFuncMinimize(TermsInput, null, _result.Terms);
}
//Запуск метода
public void Start(IEnumerable<byte[]> TermsInput, IEnumerable<byte[]> NegativTerms)
{
LogicFuncMinimize(TermsInput, NegativTerms, _result.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 PrintResult()
{
Console.WriteLine("--------Otvet-------");
char[] pTermSymbs = new char[] { '0', '1', '*' };
foreach (byte[] Term in _result.Terms)
{
for (int j = 0; j < Term.Length; j++)
{
Console.Write(pTermSymbs[Term[j]].ToString() + " ");
}
Console.WriteLine();
}
}
}
Класс Quine_McCluskey является реализацией этого алгоритма, который использует другие классы и интерфейсы: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Для запуска оптимизации нужно вызывать один из перегруженных методов Start, который вызывает функцию LogicFuncMinimize, где реализован, собственно, алгоритм минимизации. Механизм минимизации реализован в двух вариантах:
• с использованием контейнера .NET SortedSet для хранения и поиска термов.
• без использования контейнеров .NET на основе троичного дерева TreeFuncTerm.
По скорости эти два варианта примерно равны (с контейнерами .NET, возможно, чуть быстрее, но далеко не всегда), но необходимость реализации TreeFuncTerm обусловлен несколькими факторами:
• Первый вариант, основанный на 64-х битных целочисленных хэш-кодах и поиске в .NET словаре SortedSet, работает корректно только при количестве входных переменных в термах до 40, а при большем их количестве выходит за 64 битную разрядную сетку целочисленного хэш-кода, используемого для работы контейнера. Действительно, т. к. в склеенных термах внутри алгоритма применяется троичная логика, то при количестве входных переменных равном 41 максимальное значение хэш-кода уже превышает максимальное значение -1, которое можно записать в 64 битную переменную. При большем количестве переменных используется вариант, основанный на авторском троичном поисковом дереве TreeFuncTerm.
• Нужно проверять работу реализации на контейнерах .NET другой независимой от неё реализацией свободной от них.
• Просто нужен вариант, свободный от контейнеров .NET, который можно было бы легко реализовать на платформах, где нет платформы .NET (например в микроконтроллерах, ПЛИС и т. п.).
Работа поискового дерева TreeFuncTerm основана на конфигурации ссылок классов TreeNodeMiddle и TreeNodeEnd, являющихся реализациями интерфейса TreeNodeBase. Класс TreeNodeMiddle является промежуточным узлом дерева, а класс TreeNodeEnd – оконечным листом дерева. В дереве с помощью функций EnumerationInit() и EnumerationNextNode() реализован нерекурсивный механизм перебора всех конечных листьев TreeNodeEnd. Функция EnumerationInit() инициализирует перебор и возвращает первый попавшийся лист дерева. Функция EnumerationNextNode() возвращает следующий лист дерева или NULL, если листьев для выборки больше нет. При этом вспомогательная внутренняя структура EnumerationTerm, которая отражает положение поискового «курсора» внутри дерева, является также кодом терма найденного листа в троичной логике {0,1,2}. Следует заметить, что порядок выборки листьев из дерева не совпадает с порядком добавления их в него.
Алгоритм по функциональному назначению можно разбить на три этапа.
- Подготовка. Для решения указанной выше проблемы устранения перебора вариантов доопределений в рассматриваемой реализации на вход алгоритма в функцию LogicFuncMinimize поступают два исходных набора данных PositivTerms и NegativTerms, на которых оптимизируемая функция принимает, соответственно, истинное (TRUE, 1) и ложное (FALSE, 0) значения. Прежде всего, эти списки проверяются на непротиворечивость исходных данных. Необходимо, чтобы каждый из наборов данных гарантированно содержал только уникальные термы, которые присутствуют только в каком либо одном из списков. Для гарантирования этого просматривается каждый уникальный входной терм и находится количество его вхождений в каждый из исходных списков. В случае если терм встречается в обоих списках, то он остаётся только в том списке, в котором он встречается больше, а из другого — удаляется. Если же терм встречается в каждом из списков одинаково часто, то он удаляется из обоих списков, чем и обеспечивается уникальность.
- Склеивание. Далее производится итерационный цикл склейки входных терм. На каждой итерации в склеивавшихся термах добавляется по одному знаку * склеенной позиции. Поэтому количество итераций не может быть больше чем количество переменных N. В отличие от предыдущей реализации в функцию Skleivanie склеивания входных терм добавлена возможность склеивания не только с термами из своего списка, но и в случае отсутствия в нём терм с одним различием также с так называемыми «виртуальными» термами. Под «виртуальными» термами подразумеваются искусственно доопределённые термы, которых нет ни в одном из списков терм набора текущего уровня. Но склейка возможна только в том случае, если «виртуальный» терм не покрывает ни одного терма исходного набора противоположного списка.
Функция Skleivanie вызывается для обработки списков на каждой итерации два раза так, что в первом вызове смысл использования списков PositivTerms и NegativTerms совпадает с их реальным наполнением, а во втором вызове списки PositivTerms и NegativTerms по смыслу использования меняются местами, т. е. считается, что список PositivTerms содержит отрицательные термы, а список NegativTerms – положительные:
Skleivanie(X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, …);
Skleivanie(X1NegativTree, ..., X1PositivTree, ..., null, …);
Таким образом, происходит одновременная взаимозависимая склейка терм двух списков.
Если для терма не находится другого отличающегося от него только в одной позиции терма ни реального ни виртуального, т. е. терм ни с кем не склеивается, то он считается одним из результатов работы п. 1 алгоритма, исключается из дальнейшей работы в нём и поступает на вход этапа 2 работы алгоритма, реализованного в процедуре ReduceRedundancyTerms. Не склеенные термы поступают на выход алгоритма только на том вызове функции Skleivanie, для которой смысл использования списков PositivTerms и NegativTerms совпадает с их реальным наполнением, т. е. на первом вызове. - Сокращение. Отбрасывание избыточных склеенных терм в ReduceRedundancyTerms осуществляется с помощью алгоритма приближенного решения задачи о покрытии исходного множества подмножествами переменной длины. Покрытие, близкое к кратчайшему даёт алгоритм преобразования таблицы покрытий (ТП), основанный на методе “минимальный столбец–максимальная строка” (который можно посмотреть, например, здесь http://www.studfiles.ru/preview/5175815/page:4).
Приблизительная логика его работы состоит в следующем:
0. Исходная таблица считается текущей преобразуемой ТП, множество строк покрытий – пусто;
1. В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу.
2. Если в таблице есть не вычеркнутые столбцы, то выполняется п. 1, иначе – покрытие построено. Примечание: При подсчёте числа единиц в строке учитываются единицы в невычеркнутых столбцах.
Этот алгоритм работает достаточно быстро и даёт результат близкий к оптимальному.
Для проверки работы алгоритма предлагается использовать тестовую функцию TestQuineMcCluskeyRandomPart, которая из всей совокупности возможных термов количеством случайным образом выбирает только заданную часть 0<dPart<=1 (является параметром функции), для которой и производится оптимизация. При величине параметра dPart < 1 будет получаться усеченный набор входных термов, а при dPart=1 – полный набор исходных данных.
TestQuineMcCluskeyRandomPart (нажать для просмотра)
public static void TestQuineMcCluskeyRandomPart(int iVariableAmount, double dPart=1)
{
if (dPart < 0) throw new
ArgumentException("Параметр dPart должен быть больше 0 и меньше 1");
if (dPart > 1) dPart = 1;
//Получение исходных термов
ulong iTotalCombines = (ulong)1 << iVariableAmount;
LinkedList<byte[]> pTrueCol = new LinkedList<byte[]>();
LinkedList<byte[]> pFalseCol = new LinkedList<byte[]>();
HashSet<ulong> pUsedTerms = new HashSet<ulong>();
Random rnd = new Random();
byte[] buf = new byte[8];
while (pUsedTerms.LongCount() < (iTotalCombines * dPart))
{
rnd.NextBytes(buf);
ulong iCurValue = (ulong)BitConverter.ToInt64(buf, 0) % iTotalCombines;
if (pUsedTerms.Contains(iCurValue))
{
//Разрешение коллизии - последовательный поиск пустого места
do {
iCurValue = ++iCurValue % iTotalCombines;
} while (pUsedTerms.Contains(iCurValue));
}
pUsedTerms.Add(iCurValue);
byte[] sLine = new byte[iVariableAmount];
for (int i = 0; i < iVariableAmount; i++)
{
sLine[i] += (byte)(iCurValue % 2);
iCurValue >>= 1;
}
if (rnd.Next(2) != 0)
{
pTrueCol.AddLast(sLine);
}
else
{
pFalseCol.AddLast(sLine);
}
}
//Запуск в обучение
DateTime DtStart = DateTime.Now;
Console.WriteLine("Старт - " + DtStart.ToLongTimeString());
Quine_McCluskey Logic = new Quine_McCluskey();
Logic.Start(pTrueCol, pFalseCol);
DateTime DtEnd = DateTime.Now;
Logic.PrintResult();
Console.WriteLine("Старт - " + DtStart.ToLongTimeString());
Console.WriteLine("Завершение - " + DtEnd.ToLongTimeString());
TimeSpan Elapsed = DtEnd - DtStart;
Console.WriteLine("Длительность - " + String.Format("{0:00}:{1:00}:{2:00}",
Elapsed.Hours, Elapsed.Minutes, Elapsed.Seconds));
//Получение результатов
int iErrorsCounter = 0;
foreach (byte[] kvp in pTrueCol)
{
if (Logic.Result.Calculate(kvp) != true) iErrorsCounter++;
}
foreach (byte[] kvp in pFalseCol)
{
if (Logic.Result.Calculate(kvp) != false) iErrorsCounter++;
}
Console.WriteLine("Кол-во входных термов = " + pUsedTerms.Count);
Console.WriteLine("Кол-во дизъюнктивных термов = " + Logic.Result.Terms.Count);
Console.WriteLine("Кол-во ошибок = " + iErrorsCounter);
Console.ReadLine();
}
В результате работы тестовой функции рассчитывается количество термов в минимальной дизъюнктивной нормальной форме и количество ошибок покрытия ею исходного набора терм.
В заключение хотелось отметить, что на практике эта реализация алгоритма показала себя эффективным и надёжным средством минимизации логических функций, заданных двумя неполными наборами терм, на которых логическая функция принимает соответственно TRUE и FALSE значения. Конечно, также эту реализацию можно использовать в классическом виде в случае полностью определённой входной логической функции, когда на вход подаётся только один тот или иной список термов. В качестве недостатка можно отметить необходимость проверки в функции Skleivanie отсутствия ошибок покрытия для каждого виртуального терма всего списка исходных термов на каждой итерации алгоритма, что приводит к существенным временным затратам при большом количестве входных термов.