Degun Sep 26 2018 at 18:16

Реализация минимизации логических функций методом Квайна\Мак-Класки при неполном входном наборе

23 min

7.9K

.NET*Data Mining*Algorithms*C#*Machine learning*

Данная статья является, в некоторой степени, продолжением моей статьи по минимизации логических функций методом Квайна-Мак’Класки (https://habr.com/post/328506). В ней рассматривался случай с полностью определёнными логическими функциями (хотя этого в ней прямо не упоминалось, а только подразумевалось). В реальности такой случай встречается достаточно редко, когда количество входных переменных мало. Частично или не полностью определенными называются логические функции, значения которых заданы лишь для части Q из полного множества P= $inline$ возможных наборов (термов) их аргументов (переменных) количеством N, т. е. Q < P. Такая ситуация встречается на практике в большинстве случаев применений алгоритмов оптимизации логических функций. Действительно, например, если число входных переменных N=30, что является заурядным случаем, например на финансовых рынках, то объём входной обучающей выборки должен составлять порядка $2^{30}$ > $inline$ элементарных уникальных термов. Такой массив данных встречается не в каждой даже очень крупной организации, не говоря уже о частных лицах, т. е. это уже сфера BigData, использования ЦОД-ов и т. д.

Поэтому на практике чаще всего минимизируемые логические функции будут определены не полностью просто в силу отсутствия необходимого количества накопленных данных или в силу разных других объективных причин (например, не хватает места для их хранения). Возникает вопрос о возможности «обхода» этой неприятности при использовании алгоритма, работающего с полностью определённым набором терм логической функции, таким как, например, из предыдущей моей статьи.

Стандартной практикой в этом случае является доопределение неполного входного набора значений переменных (термов) до полного таким образом, чтобы оно давало оптимальный результат для имеющегося набора данных. Но, в этом случае, возникает проблема в переборе всех возможных вариантов доопределений, общее количество которых составляет V= $2^{P-Q}$ , чтобы выбрать оптимальный вариант доопределения в соответствии с заданным критерием. Очевидно, что для реально используемых значений 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;

#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
{
  // Конечный узел дерева термов
  public class TreeNodeEnd { }
  //Общий конечный узел дерева
  private readonly TreeNodeEnd pCommonTreeNodeEnd = new TreeNodeEnd();

  //Корень
  private readonly object[] rootNode = new object[3];
  //Режим работы дерева в отношении конечных узлов
  private readonly bool IsNewTreeNodeEndMode = false;
  //Ранг (глубина) дерева
  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 TreeNodeEnd enumerationNode;
  public TreeNodeEnd EnumerationNode
  {
    get { return enumerationNode; }
  }
  //Возвращает количество термов в дереве
  private UInt32 _count = 0;
  public UInt32 Count
  {
    get { return _count; }
  }

  //Конструктор
  public TreeFuncTerm(bool bNewTreeNodeEndMode = false)
  {
    IsNewTreeNodeEndMode = bNewTreeNodeEndMode;
    Clear();
  }

  //Очистить дерево
  public void Clear()
  {
    _count = 0;
    _rang = 0;
    enumerationPos = 0;
    enumerationBuf = null;
    enumerationTerm = null;
    enumerationNode = null;
    rootNode[0] = rootNode[1] = rootNode[2] = null;
  }

  //Инициализировать процесс перебора конечных узлов дерева
  public TreeNodeEnd EnumerationInit()
  {
    enumerationPos = 0;
    enumerationTerm = new byte[_rang];
    enumerationTerm[0] = 0;
    enumerationNode = null;
    enumerationBuf = new object[_rang][];
    enumerationBuf[0] = rootNode;
    //Вернуть первый конечный узел
    return EnumerationNextNode();
  }

  //Получить следующий конечный узел дерева
  public TreeNodeEnd EnumerationNextNode()
  {
    int iIsNext = (enumerationNode != null ? 1 : 0);
    enumerationNode = null;
    while ((enumerationNode == null) && (enumerationPos >= 0))
    {
      object pNextNode = null;
      int iSymb = enumerationTerm[enumerationPos] + iIsNext;
      for (object[] pNodes = enumerationBuf[enumerationPos]; iSymb < 3; iSymb++)
      {
        if ((pNextNode = pNodes[iSymb]) != null) break;
      }
      if (pNextNode == null)
      {
        //Возврат на предыдущий уровень
        enumerationPos--;
        iIsNext = 1;
      }
      else
      {
        enumerationTerm[enumerationPos] = (byte)iSymb;
        if (pNextNode is TreeNodeEnd)
        {
          //Найден конечный узел
          enumerationNode = (TreeNodeEnd)pNextNode;
        }
        else
        {
          //Переход на следующий уровень
          enumerationPos++;
          enumerationBuf[enumerationPos] = (object[])pNextNode;
          enumerationTerm[enumerationPos] = 0;
          iIsNext = 0;
        }
      }
    }
    return enumerationNode;
  }

  //Добавление в дерево нового терма без замены имеющегося
  public TreeNodeEnd Add(byte[] term)
  {
    _rang = Math.Max(_rang, term.Length);
    object[] pCurrNode = rootNode;
    int iTermLength1 = term.Length - 1;
    for (int i = 0; i < iTermLength1; i++)
    {
      byte cSymb = term[i];
      object pNextNode = pCurrNode[cSymb];
      if (pNextNode == null)
      {
        pNextNode = new object[3];
        pCurrNode[cSymb] = pNextNode;
      }
      pCurrNode = (object[])pNextNode;
    }
    object pNewNode = pCurrNode[term[iTermLength1]];
    if (pNewNode == null)
    {
      pNewNode = (IsNewTreeNodeEndMode ? new TreeNodeEnd() : pCommonTreeNodeEnd);
      pCurrNode[term[iTermLength1]] = pNewNode;
      _count++;
    }
    return (TreeNodeEnd)pNewNode;
  }

  //Удаление из контейнера конечного узла последовательности
  public TreeNodeEnd Remove(byte[] term)
  {
    object[] pCurrNode = rootNode;
    int iTermLength1 = term.Length - 1;
    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 void Remove(IEnumerable<byte[]> RemovedTerms)
  {
    if ((RemovedTerms == null) || (RemovedTerms.Count() == 0)) return;
    foreach (byte[] x1 in RemovedTerms)
    {
      //Из-за особенностей работы функции можно сразу вызывать Remove
      //без предварительного вызова IsContains
      Remove(x1);
    }
  }

  //Проверка нахождения последовательности в контейнере
  public bool Contains(byte[] term)
  {
    object pCurrNode = rootNode;
    for (int i = 0; i < term.Length; i++)
    {
      pCurrNode = ((object[])pCurrNode)[term[i]];
      if (pCurrNode == null) break;
    }
    return ((pCurrNode != null) && (pCurrNode is TreeNodeEnd));
  }

  //Проверка присутствия последовательностей в контейнере,
  //дающих истинное значение для входного терма
  public bool IsCalculateTrue(byte[] term)
  {
    return IsCalculateTrue(rootNode, term, 0);
  }

  //рекурсивная версия предыдущей функции
  private static bool IsCalculateTrue(object[] pCurrNode, byte[] term, int iStartPos)
  {
    int iTermLength1 = term.Length - 1;
    while ((pCurrNode != null) && (iStartPos < iTermLength1))
    {
      byte cSymb = term[iStartPos++];
      if (cSymb != LogicFunction.cStarSymb)
      {
        pCurrNode = (object[])pCurrNode[cSymb];
      }
      else
      {
        if ((pCurrNode[0] != null) && (pCurrNode[1] != null))
        {
          if (IsCalculateTrue((object[])pCurrNode[1], term, iStartPos)) return true;
          pCurrNode = (object[])pCurrNode[0];
        }
        else
        {
          pCurrNode = (object[])(pCurrNode[0] != null ? pCurrNode[0] : pCurrNode[1]);
        }
      }
    }
    TreeNodeEnd pEndNode = null;
    if (pCurrNode != null)
    {
      byte cSymb = term[iTermLength1];
      if (cSymb != LogicFunction.cStarSymb)
      {
        pEndNode = (TreeNodeEnd)pCurrNode[cSymb];
      }
      else
      {
        pEndNode = (TreeNodeEnd)(pCurrNode[0] != null ? pCurrNode[0] : pCurrNode[1]);
      }
    }
    return (pEndNode != null);
  }

  //Получение всех последовательностей в контейнере,
  //дающих истинное значение для входного терма
  public void GetAllCalculateTrueTerms(byte[] term, ICollection<TreeNodeEnd> pAllCalculateTrueTermsList)
  {
    pAllCalculateTrueTermsList.Clear();
    GetAllCalculateTrueTerms(rootNode, term, 0, pAllCalculateTrueTermsList);
  }

  //рекурсивная версия предыдущей функции
  private static void GetAllCalculateTrueTerms(object[] pCurrNode, byte[] term, int iStartPos,
    ICollection<TreeNodeEnd> pAllCalculateTrueTermsList)
  {
    int iTermLength1 = term.Length - 1;
    while ((pCurrNode != null) && (iStartPos < iTermLength1))
    {
      byte cSymb = term[iStartPos++];
      if (cSymb != LogicFunction.cStarSymb)
      {
        pCurrNode = (object[])pCurrNode[cSymb];
      }
      else
      {
        if ((pCurrNode[0] != null) && (pCurrNode[1] != null))
        {
          GetAllCalculateTrueTerms((object[])pCurrNode[1], term, iStartPos, pAllCalculateTrueTermsList);
          pCurrNode = (object[])pCurrNode[0];
        }
        else
        {
          pCurrNode = (object[])(pCurrNode[0] != null ? pCurrNode[0] : pCurrNode[1]);
        }
      }
    }
    if (pCurrNode != null)
    {
      byte cSymb = term[iTermLength1];
      if (cSymb != LogicFunction.cStarSymb)
      {
        TreeNodeEnd pEndNode = (TreeNodeEnd)pCurrNode[cSymb];
        if (pEndNode != null) pAllCalculateTrueTermsList.Add(pEndNode);
      }
      else
      {
        if (pCurrNode[0] != null) pAllCalculateTrueTermsList.Add((TreeNodeEnd)pCurrNode[0]);
        if (pCurrNode[1] != null) pAllCalculateTrueTermsList.Add((TreeNodeEnd)pCurrNode[1]);
      }
    }
  }
}

/// <summary>
/// Минимизация логической функции методом Квайна---Мак-Класки
/// </summary>
public class Quine_McCluskey
{
  //Максимальное кол-во элементов, при котором используется HashSet
  private static readonly int HASHSET_MAX_ITEMS = 10000000;
  //Решение по положительным термам
  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,
    TreeFuncTerm InpNegTerms, TreeFuncTerm AllOutTerms)
  {
    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 == 0)
          {
            pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
            X2Tree.Add(pCurrTerm);
          }
        }
        //или склеивание с виртуальной термой, которой нет в NegativTree
        else if (IsVirtSkleivOn && !NegativTree.Contains(pCurrTerm))
        {
          pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
          /*bool bIsNotCanAdd = false;
          foreach (byte[] NegTerm in InpNegTerms)
          {
            if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break;
          }
          if (!bIsNotCanAdd)*/
          if (!InpNegTerms.IsCalculateTrue(pCurrTerm))
          {
            bIsSkleiv = true;
            X2Tree.Add(pCurrTerm);
          }
        }
        pCurrTerm[iPos] = cSymbSav;
      }
      //Добавление на выход тех термов, которые ни с кем не склеились
      if (!bIsSkleiv && (AllOutTerms != null)) AllOutTerms.Add(pCurrTerm);
    }
  }

  //Возвращает уникальный код для терма
  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;
      iMultip = (iMultip << 1) + iMultip;
    }
    return iCode;
  }

  //Возвращает терм для уникального кода
  private static void GetTermByCode(UInt64 iCode, byte[] pTerm)
  {
    int iCounter = 0;
    while (iCode != 0)
    {
      pTerm[iCounter++] = (byte)(iCode % 3);
      iCode /= 3;
    }
    while (iCounter < pTerm.Length) pTerm[iCounter++] = 0;
  }

  //Склеивание строк с одним различием
  private static void Skleivanie(ICollection<UInt64> X1Tree, ICollection<UInt64> X2Tree,
    ICollection<UInt64> NegativTree, TreeFuncTerm InpNegTerms, TreeFuncTerm AllOutTerms,
    int iTermLength, UInt64[] MultiVals)
  {
    bool IsVirtSkleivOn = ((NegativTree != null) && (InpNegTerms != null) && (InpNegTerms.Count != 0));
    byte[] pCurrTerm = new byte[iTermLength];
    foreach (UInt64 x1 in X1Tree)
    {
      GetTermByCode(x1, pCurrTerm);
      bool bIsSkleiv = false;
      for (int iPos = 0; iPos < iTermLength; iPos++)
      {
        byte cSymbSav = pCurrTerm[iPos];
        if (cSymbSav != LogicFunction.cStarSymb)
        {
          UInt64 iMultip = MultiVals[iPos];
          UInt64 iCode = (cSymbSav == 0 ? x1 + iMultip : x1 - iMultip);
          //Склеивание двух термов с одним различием
          if (X1Tree.Contains(iCode))
          {
            bIsSkleiv = true;
            if (cSymbSav == 0)
            {
              //iCode = x1 + (byte)(LogicFunction.cStarSymb - cSymbSav) * iMultip;
              iCode += iMultip;
              X2Tree.Add(iCode);
            }
          }
          //или склеивание с виртуальной термой, которой нет в NegativTree
          else if (IsVirtSkleivOn && !NegativTree.Contains(iCode))
          {
            pCurrTerm[iPos] = LogicFunction.cStarSymb; //Метка склеивания
            /*bool bIsNotCanAdd = false;
            foreach (byte[] NegTerm in NegTerms)
            {
              if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break;
            }
            if (!bIsNotCanAdd)*/
            if (!InpNegTerms.IsCalculateTrue(pCurrTerm))
            {
              bIsSkleiv = true;
              //iCode = x1 + (byte)(LogicFunction.cStarSymb - cSymbSav) * iMultip;
              iCode += (cSymbSav == 0 ? iMultip : (iMultip << 1));
              X2Tree.Add(iCode);
            }
            pCurrTerm[iPos] = cSymbSav;
          }
        }
      }
      //Добавление на выход тех термов, которые ни с кем не склеились
      if (!bIsSkleiv && (AllOutTerms != null)) AllOutTerms.Add(pCurrTerm);
    }
  }

  //Удаление дубликатов термов из входного списка
  //В выходной словарь добавляются только уникальные термы
  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)) OutX2Tree.Add(iCode);
    }
  }

  //Удаление дубликатов термов из входного списка
  //В выходное дерево добавляются только уникальные термы
  private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, TreeFuncTerm OutX2Tree)
  {
    OutX2Tree.Clear();
    foreach (byte[] x1 in InX1) OutX2Tree.Add(x1);
  }

  // Отбрасывание избыточных терм с помощью алгоритма приближенного решения задачи о покрытии.
  // Покрытие, близкое к кратчайшему, даёт следующий алгоритм преобразования таблицы покрытий (ТП),
  // основанный на методе “минимальный столбец–максимальная строка” (http://www.studfiles.ru/preview/5175815/page:4/):
  private static void ReduceRedundancyTerms(TreeFuncTerm AllOutputTerms,
    TreeFuncTerm AllInputTerms, ICollection<byte[]> ResultTerms)
  {
    //Подготовка результирующего контейнера
    ResultTerms.Clear();
    //Контейнер для соответствия конечного терма к списку первичных термов, которые его образовали
    Dictionary<byte[], HashSet<TreeFuncTerm.TreeNodeEnd>> Outputs2Inputs = new Dictionary<byte[], HashSet<TreeFuncTerm.TreeNodeEnd>>();
    //Контейнер для соответствия первичных входных терм к тем выходным, которые их покрывают
    Dictionary<TreeFuncTerm.TreeNodeEnd, HashSet<byte[]>> Inputs2Outputs = new Dictionary<TreeFuncTerm.TreeNodeEnd, HashSet<byte[]>>();
    //Сбор статистики об покрытии выходными термами входных
    for (TreeFuncTerm.TreeNodeEnd pNode = AllOutputTerms.EnumerationInit(); pNode != null; pNode = AllOutputTerms.EnumerationNextNode())
    {
      byte[] outTerm = (byte[])AllOutputTerms.EnumerationTerm.Clone();
      //Контейнер входных термов, которые покрывает данный выходной терм term
      HashSet<TreeFuncTerm.TreeNodeEnd> InpTermsLst = new HashSet<TreeFuncTerm.TreeNodeEnd>();
      AllInputTerms.GetAllCalculateTrueTerms(outTerm, InpTermsLst);
      Outputs2Inputs.Add(outTerm, InpTermsLst);
      foreach (TreeFuncTerm.TreeNodeEnd inputTerm in InpTermsLst)
      {
        if (!Inputs2Outputs.ContainsKey(inputTerm)) Inputs2Outputs.Add(inputTerm, new HashSet<byte[]>());
        Inputs2Outputs[inputTerm].Add(outTerm);
      }
    }
    //Сортировка словаря исходных термов по возрастанию кол-ва их покрытий выходными
    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 (TreeFuncTerm.TreeNodeEnd inTerm in Outputs2Inputs[outTerm].ToArray())
      {
        foreach (byte[] outTerm2Del in Inputs2Outputs[inTerm]) Outputs2Inputs[outTerm2Del].Remove(inTerm);
        Inputs2Outputs.Remove(inTerm);
      }
    }
  }

  //Нахождение минимальной логической функции
  public static void LogicFuncMinimize(
    IEnumerable<byte[]> PositivTerms, ICollection<byte[]> OutPos,
    IEnumerable<byte[]> NegativTerms, ICollection<byte[]> OutNeg)
  {
    TreeFuncTerm InpPosTerms = new TreeFuncTerm(true);
    DeleteDublicatingTerms(PositivTerms, InpPosTerms);

    int iTotalLevels = InpPosTerms.Rang;
    if (iTotalLevels <= 0) return;

    TreeFuncTerm OutPosTerms = new TreeFuncTerm();
    TreeFuncTerm OutNegTerms = null;

    TreeFuncTerm InpNegTerms = null;
    if ((NegativTerms != null) && (NegativTerms.Count() != 0))
    {
      InpNegTerms = new TreeFuncTerm(true);
      DeleteDublicatingTerms(NegativTerms, InpNegTerms);
      OutNegTerms = new TreeFuncTerm();

      //Проверка наличия и удаление одинаковых данных в обеих последовательностях
      for (TreeFuncTerm.TreeNodeEnd pNode = InpPosTerms.EnumerationInit();
        pNode != null; pNode = InpPosTerms.EnumerationNextNode())
      {
        if (!InpNegTerms.Contains(InpPosTerms.EnumerationTerm)) continue;
        //Подсчитывается кол-во входных термов в X1 и в NegativTerms
        int iPos_Count = PositivTerms.Count(p => Enumerable.SequenceEqual(p, InpPosTerms.EnumerationTerm));
        int iNeg_Count = NegativTerms.Count(p => Enumerable.SequenceEqual(p, InpPosTerms.EnumerationTerm));
        if (iPos_Count > iNeg_Count)
        {
          InpNegTerms.Remove(InpPosTerms.EnumerationTerm);
        }
        else if (iPos_Count < iNeg_Count)
        {
          InpPosTerms.Remove(InpPosTerms.EnumerationTerm);
        }
        else //if (iX1_Count == iNeg_Count)
        {
          InpPosTerms.Remove(InpPosTerms.EnumerationTerm);
          InpNegTerms.Remove(InpPosTerms.EnumerationTerm);
        }
      }
    }

    if (iTotalLevels < 40)
    {
      ICollection<UInt64> X1PositivTree = (InpPosTerms.Count <= HASHSET_MAX_ITEMS ?
        (ICollection<UInt64>)(new HashSet<UInt64>()) : new SortedSet<UInt64>());
      for (TreeFuncTerm.TreeNodeEnd pNode = InpPosTerms.EnumerationInit();
        pNode != null; pNode = InpPosTerms.EnumerationNextNode())
      {
        X1PositivTree.Add(GetTermCode(InpPosTerms.EnumerationTerm));
      }

      ICollection<UInt64> X1NegativTree = null;
      if (InpNegTerms != null)
      {
        X1NegativTree = (InpNegTerms.Count <= HASHSET_MAX_ITEMS ?
          (ICollection<UInt64>)(new HashSet<UInt64>()) : new SortedSet<UInt64>());
        for (TreeFuncTerm.TreeNodeEnd pNode = InpNegTerms.EnumerationInit();
          pNode != null; pNode = InpNegTerms.EnumerationNextNode())
        {
          X1NegativTree.Add(GetTermCode(InpNegTerms.EnumerationTerm));
        }
      }

      //Таблица значений множителей для перевода из числа UInt64 в массив byte[] и обратно
      UInt64[] pMultiVals = new UInt64[iTotalLevels];
      UInt64 iMultip = 1;
      for (int i = 0; i < iTotalLevels; i++)
      {
        pMultiVals[i] = iMultip;
        iMultip *= 3;
      }

      int iLevelCounter = 0;
      //Повтор до тех пор пока будут оставаться термы
      while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels))
      {
        ICollection<UInt64> X2PositivTree = (X1PositivTree.Count <= HASHSET_MAX_ITEMS ?
          (ICollection<UInt64>)(new HashSet<UInt64>()) : new SortedSet<UInt64>());
        Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms,
          OutPosTerms, iTotalLevels, pMultiVals);

        if ((X1NegativTree != null) && (X1NegativTree.Count != 0))
        {
          ICollection<UInt64> X2NegativTree = (X1NegativTree.Count <= HASHSET_MAX_ITEMS ?
            (ICollection<UInt64>)(new HashSet<UInt64>()) : new SortedSet<UInt64>());
          Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms,
            OutNegTerms, iTotalLevels, pMultiVals);

          //Очистка поискового словаря
          X1NegativTree.Clear();

          X1NegativTree = X2NegativTree;
        }

        //Очистка поискового словаря
        X1PositivTree.Clear();

        X1PositivTree = X2PositivTree;

        iLevelCounter++;

        GC.Collect();
      }
    }
    else
    {
      //Исходные деревья
      TreeFuncTerm X1PositivTree = InpPosTerms;
      TreeFuncTerm X1NegativTree = InpNegTerms;

      int iLevelCounter = 0;
      //Повтор до тех пор пока будут оставаться термы
      while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels))
      {
        TreeFuncTerm X2PositivTree = new TreeFuncTerm();
        Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms, OutPosTerms);

        if ((X1NegativTree != null) && (X1NegativTree.Count != 0))
        {
          TreeFuncTerm X2NegativTree = new TreeFuncTerm();
          Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms, OutNegTerms);

          //Очистка поискового дерева
          if (iLevelCounter > 0) X1NegativTree.Clear();

          X1NegativTree = X2NegativTree;
        }

        //Очистка поискового дерева
        if (iLevelCounter > 0) X1PositivTree.Clear();

        X1PositivTree = X2PositivTree;

        iLevelCounter++;

        GC.Collect();
      }
    }
    if (OutPosTerms.Count > 0)
    {
      //Удаляется терм, содержащий во всех позициях cStarSymb
      OutPosTerms.Remove(Enumerable.Repeat(LogicFunction.cStarSymb, iTotalLevels).ToArray());
    }
    //Выбор оптимального набора терм
    ReduceRedundancyTerms(OutPosTerms, InpPosTerms, OutPos);

    if ((OutNeg != null) && (OutNegTerms != null))
    {
      if (OutNegTerms.Count > 0)
      {
        //Удаляется терм, содержащий во всех позициях cStarSymb
        OutNegTerms.Remove(Enumerable.Repeat(LogicFunction.cStarSymb, iTotalLevels).ToArray());
      }
      //Выбор оптимального набора терм
      ReduceRedundancyTerms(OutNegTerms, InpNegTerms, 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()));
  }
}

Класс Quine_McCluskey является реализацией этого алгоритма, который использует другие классы и интерфейсы: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Для запуска оптимизации нужно вызывать один из перегруженных методов Start, который вызывает функцию LogicFuncMinimize, где реализован, собственно, алгоритм минимизации. Механизм минимизации реализован в двух вариантах:
• с использованием контейнера .NET SortedSet для хранения и поиска термов.
• без использования контейнеров .NET на основе троичного дерева TreeFuncTerm.

По скорости эти два варианта примерно равны (с контейнерами .NET, возможно, чуть быстрее, но далеко не всегда), но необходимость реализации TreeFuncTerm обусловлен несколькими факторами:
• Первый вариант, основанный на 64-х битных целочисленных хэш-кодах и поиске в .NET словаре SortedSet, работает корректно только при количестве входных переменных в термах до 40, а при большем их количестве выходит за 64 битную разрядную сетку целочисленного хэш-кода, используемого для работы контейнера. Действительно, т. к. в склеенных термах внутри алгоритма применяется троичная логика, то при количестве входных переменных равном 41 максимальное значение хэш-кода $3^{41}$ уже превышает максимальное значение $2^{64}$ -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, которая из всей совокупности возможных термов количеством $inline$ случайным образом выбирает только заданную часть 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 отсутствия ошибок покрытия для каждого виртуального терма всего списка исходных термов на каждой итерации алгоритма, что приводит к существенным временным затратам при большом количестве входных термов.

Tags:

Hubs: