How to become an author
Search
Write a publication
Pull to refresh

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

Reading time16 min
Views22K
Data Mining*Algorithms*C#*Machine learning*
From sandbox
К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических (булевых) функций (ЛФ) заданных в виде совершенной дизъюнктивной нормальной формы (СДНФ) методом Квайна\Мак-Класки (далее просто Мак-Класки) и проблемы, выявленные при её тестировании. В исследуемом варианте алгоритм Мак-Класки реализован на языке C# с использованием Generic-коллекций библиотеки .NET.

Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. к. по своему смыслу она реализует процедуру обучения с учителем для определённого набора входных терм (простых конъюнкций), на которых оптимизируемая функция принимает истинное (true) значение. Следовательно, этот набор входных терм, из общего их возможного числа $2^N$, где N – количество двух классовых категориальных (двоичных) переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным (данном случае истинным) выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное (false) значение.

Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак-Класки. Согласно теории метод Мак-Класки состоит из двух основных этапов:

  1. Нахождение всех простых терм ЛФ, используя правило (законы) склеивания:
    a) (A & B) ∨ (A & !B) ≡ A;
    b) (A ∨ B) & (A ∨ !B) ≡ A;
    где & — операция логического «И»; ∨ — операция логического «ИЛИ»;! – операция логического отрицания «НЕ».

  2. Минимизация количества простых терм полученного множества, как задача нахождения оптимального покрытия множества подмножествами разной длины.

Код реализации следующий (нажать для просмотра): 
using System;
using System.IO;
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 abstract bool Calculate(char[] X);
  //Вычисление значения функции
  public abstract bool Calculate(byte[] X);
}

/// <summary>
/// Дизъюнктивная нормальная форма
/// </summary>
public class Dnf : LogicFunction
{
  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;
  }
}

/// <summary>
/// Минимизация логической функции методом Квайна\Мак-Класки
/// </summary>
public class Quine_McCluskey
{
  //Максимальное кол-во элементов, при котором используется Dictionary,
  //чтобы не произошло переполнение максимальной ёмкости контейнера
  private static readonly int DICT_MAX_ITEMS = 8000000;

  //Коллекция "склеенных" термов
  private readonly Dnf _result = new Dnf();
  public Dnf Result
  {
    get { return _result; }
  }

  //Запуск метода
  public void Start(IEnumerable<byte[]> TermsInput)
  {
    LogicFuncMinimize(TermsInput, _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<bool[]> TermsInput)
  {
    Start(TermsInput.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray()));
  }

  //Запуск метода с чтением ДСНФ из файла
  public void Start(string sFileName)
  {
    Start(LoadDsnfFromFile(sFileName));
  }

  //Нахождение минимальной логической функции
  private static void LogicFuncMinimize(
    IEnumerable<byte[]> InpTerms, ICollection<byte[]> OutTerms)
  {
    LinkedList<TreeNodeEnd> OutTemp = new LinkedList<TreeNodeEnd>();
    if (InpTerms.First().Length < 40)
    {
      IDictionary<UInt64, TreeNodeEnd> X1Tree = (InpTerms.Count() < DICT_MAX_ITEMS ?
        (IDictionary<UInt64, TreeNodeEnd>)(new Dictionary<UInt64, TreeNodeEnd>()) :
        new SortedDictionary<UInt64, TreeNodeEnd>());
      DeleteDublicatingTerms(InpTerms, X1Tree);
      //Повтор до тех пор пока будут оставаться термы
      while (X1Tree.Count != 0)
      {
        IDictionary<UInt64, TreeNodeEnd> X2Tree = (X1Tree.Count < DICT_MAX_ITEMS ?
          (IDictionary<UInt64, TreeNodeEnd>)(new Dictionary<UInt64, TreeNodeEnd>()) :
          new SortedDictionary<UInt64, TreeNodeEnd>());
        Skleivanie(X1Tree, X2Tree, OutTemp);
        X1Tree.Clear();
        X1Tree = X2Tree;
        GC.Collect(); //Сборка мусора очень сильно влияет на время работы!!!
      }
    }
    else
    {
      TreeFuncTerm X1Tree = new TreeFuncTerm();
      DeleteDublicatingTerms(InpTerms, X1Tree);
      //Повтор до тех пор пока будут оставаться термы
      while (X1Tree.Count != 0)
      {
        TreeFuncTerm X2Tree = new TreeFuncTerm();
        Skleivanie(X1Tree, X2Tree, OutTemp);
        X1Tree.Clear();
        X1Tree = X2Tree;
        GC.Collect(); //Сборка мусора очень сильно влияет на время работы!!!
      }
    }
    ReduceRedundancyTerms(OutTemp, OutTerms);
  }

  //Процедура чтения ДСНФ из файла и запись в матрицу
  private static ICollection<byte[]> LoadDsnfFromFile(string sFullFileName)
  {
    ICollection<byte[]> DSNF = new LinkedList<byte[]>();
    //Чтение строк из файла
    using (StreamReader InFile = new StreamReader(sFullFileName))
    {
      string sLine = "";
      while ((sLine = InFile.ReadLine()) != null)
      {
        DSNF.Add(sLine.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray());
      }
    }
    return DSNF;
  }

  //Удаление дубликатов термов из входного списка
  //В выходной словарь добавляются только уникальные термы
  private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1,
    IDictionary<UInt64, TreeNodeEnd> OutX2Tree)
  {
    OutX2Tree.Clear();
    foreach (byte[] x1 in InX1)
    {
      UInt64 iCode = GetTermCode(x1);
      if (OutX2Tree.ContainsKey(iCode)) continue;
      OutX2Tree.Add(iCode, new TreeNodeEnd(x1, null, null));
    }
  }

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

  //Склеивание строк с одним различием
  private static void Skleivanie(
    TreeFuncTerm X1Tree, TreeFuncTerm X2Tree,
    ICollection<TreeNodeEnd> OutResult)
  {
    Dictionary<int, TreeNodeEnd> FindTerms = new Dictionary<int, TreeNodeEnd>();
    TreeNodeEnd x1 = X1Tree.Last;
    while (x1 != null)
    {
      bool bIsSkleiv = false;
      for (int iPos = 0; iPos < x1.Term.Length; iPos++)
      {
        byte cSymbSav = x1.Term[iPos];
        if (cSymbSav == LogicFunction.cStarSymb) continue;
        //Склеивание двух термов с одним различием
        x1.Term[iPos] = (byte)(1 - cSymbSav);
        TreeNodeEnd pSkleivNode = X1Tree.Contains(x1.Term);
        if (pSkleivNode != null)
        {
          bIsSkleiv = true;
          //Проверка, чтобы комбинации термов обрабатывались только по одному разу
          if (cSymbSav == 1)
          {
            x1.Term[iPos] = LogicFunction.cStarSymb;
            X2Tree.Add(x1.Term, x1, pSkleivNode);
          }
        }
        x1.Term[iPos] = cSymbSav;
      }
      //Добавление на выход тех термов, которые ни с кем не склеились
      if (!bIsSkleiv) OutResult.Add(x1);
      //Переход к следующему листу дерева
      x1 = x1.PrevNode;
    }
  }

  //Возвращает уникальный код для терма
  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 void Skleivanie(
    IDictionary<UInt64, TreeNodeEnd> X1Tree,
    IDictionary<UInt64, TreeNodeEnd> X2Tree,
    ICollection<TreeNodeEnd> OutResult)
  {
    foreach (KeyValuePair<UInt64, TreeNodeEnd> x1 in X1Tree)
    {
      bool bIsSkleiv = false;
      UInt64 iMultip = 1;
      for (int iPos = 0; iPos < x1.Value.Term.Length; iPos++)
      {
        byte cSymbSav = x1.Value.Term[iPos];
        if (cSymbSav != LogicFunction.cStarSymb)
        {
          UInt64 iCode;
          if (cSymbSav == 0)
            iCode = x1.Key + iMultip;
          else //_if (cSymbSav == 1)
            iCode = x1.Key - iMultip;
          TreeNodeEnd pSkleivNode = null;
          X1Tree.TryGetValue(iCode, out pSkleivNode);
          if (pSkleivNode != null)
          {
            bIsSkleiv = true;
            //Проверка, чтобы комбинации термов обрабатывались только по одному разу
            if (cSymbSav == 1)
            {
              //Склеивание двух термов с одним различием
              iCode = x1.Key + iMultip;
              if (!X2Tree.ContainsKey(iCode))
              {
                x1.Value.Term[iPos] = LogicFunction.cStarSymb; //Метка склеивания
                X2Tree.Add(iCode, new TreeNodeEnd(x1.Value.Term, x1.Value, pSkleivNode));
                x1.Value.Term[iPos] = cSymbSav;
              }
            }
          }
        }
        iMultip *= 3;
      }
      //Добавление на выход тех термов, которые ни с кем не склеились
      if (!bIsSkleiv) OutResult.Add(x1.Value);
    }
  }

  //Отбрасывание избыточных терм с помощью алгоритма приближенного решения задачи о покрытии
  private static void ReduceRedundancyTerms(
    IEnumerable<TreeNodeEnd> SkleivTerms, ICollection<byte[]> ResultTerms)
  {
    //Подготовка результирующего контейнера
    ResultTerms.Clear();
    //Контейнер для соответствия конечного терма к списку первичных термов, которые его образовали
    IDictionary<TreeNodeEnd, HashSet<TreeNodeEnd>> Outputs2Inputs =
      new Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>>();
    //Контейнер для соответствия первичных входных терм к тем выходным, которые их покрывают
    IDictionary<TreeNodeEnd, HashSet<TreeNodeEnd>> Inputs2Outputs =
      new Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>>();
    //Сбор статистики об покрытии выходными термами входных
    foreach (TreeNodeEnd outTerm in SkleivTerms)
    {
      //Контейнер входных термов, которые покрывает данный выходной терм term
      HashSet<TreeNodeEnd> InpTermsLst = new HashSet<TreeNodeEnd>();
      HashSet<TreeNodeEnd> ListNumbers = new HashSet<TreeNodeEnd>();
      ListNumbers.Add(outTerm);
      while (ListNumbers.Count > 0)
      {
        TreeNodeEnd pCurrNode = ListNumbers.First();
        ListNumbers.Remove(pCurrNode);
        if (pCurrNode.Parent1 != null && pCurrNode.Parent2 != null)
        {
          ListNumbers.Add(pCurrNode.Parent1);
          ListNumbers.Add(pCurrNode.Parent2);
        }
        else
        {
          InpTermsLst.Add(pCurrNode);
          if (!Inputs2Outputs.ContainsKey(pCurrNode))
          {
            Inputs2Outputs.Add(pCurrNode, new HashSet<TreeNodeEnd>());
          }
          Inputs2Outputs[pCurrNode].Add(outTerm);
        }
      }
      Outputs2Inputs.Add(outTerm, InpTermsLst);
    }
    //Сортировка словаря исходных термов по возрастанию кол-ва их покрытий выходными
    Inputs2Outputs = Inputs2Outputs.OrderBy(p => p.Value.Count).ToDictionary(p => p.Key, v => v.Value);
    //Перебор всех входных термов, отсортированных по кол-ву покрывавших их выходных
    while (Inputs2Outputs.Count > 0)
    {
      TreeNodeEnd outTerm = Inputs2Outputs.First().Value.OrderByDescending(q => Outputs2Inputs[q].Count()).First();
      ResultTerms.Add(outTerm.Term);
      foreach (TreeNodeEnd inpTerm in Outputs2Inputs[outTerm].ToArray())
      {
        foreach (TreeNodeEnd outTerm2Del in Inputs2Outputs[inpTerm])
        {
          Outputs2Inputs[outTerm2Del].Remove(inpTerm);
        }
        Inputs2Outputs.Remove(inpTerm);
      }
    }
  }
}

/// <summary>
/// Дерево термов
/// </summary>
public class TreeFuncTerm
{
  //Корень
  private readonly TreeNodeMiddle rootNode = new TreeNodeMiddle();
  //Ссылка на завершающий узел последовательности конечных листьев дерева
  private TreeNodeEnd _lastTreeNode = null;
  public TreeNodeEnd Last
  {
    get { return _lastTreeNode; }
  }
  //Возвращает количество термов в дереве
  private int _count = 0;
  public int Count
  {
    get { return _count; }
  }

  //Конструктор
  public TreeFuncTerm()
  {
    Clear();
  }

  //Очистить дерево
  public void Clear()
  {
    rootNode.Clear();
    _count = 0;
    _lastTreeNode = null;
  }

  //Добавление в дерево нового терма
  public void Add(byte[] term, TreeNodeEnd pParent1, TreeNodeEnd pParent2)
  {
    TreeNodeMiddle pCurrNode = rootNode;
    int iTermLength1 = term.Length - 1;
    for (int i = 0; i < iTermLength1; i++)
    {
      byte cSymb = term[i];
      TreeNodeBase item = pCurrNode.Childs[cSymb];
      if (item == null)
      {
        item = new TreeNodeMiddle();
        pCurrNode.Childs[cSymb] = item;
      }
      pCurrNode = (TreeNodeMiddle)item;
    }
    TreeNodeBase pNewNode = pCurrNode.Childs[term[iTermLength1]];
    if (pNewNode == null)
    {
      pNewNode = new TreeNodeEnd(term, pParent1, pParent2, _lastTreeNode);
      pCurrNode.Childs[term[iTermLength1]] = pNewNode;
      _lastTreeNode = (TreeNodeEnd)pNewNode;
      _count++;
    }
  }

  //Проверка нахождения последовательности в контейнере
  public TreeNodeEnd Contains(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);
  }
}

/// <summary>
/// Базовый интерфейс узла дерева термов
/// </summary>
public interface TreeNodeBase
{
  //Очистка выделенных ресурсов
  void Clear();
}

/// <summary>
/// Конечный узел дерева термов
/// </summary>
public class TreeNodeEnd : TreeNodeBase
{
  //Терм, сопоставленный узлу
  public readonly byte[] Term;
  //Ссылка на предыдущий конечный узел дерева текущего уровня
  //для создания одностороннего связанного списка
  public readonly TreeNodeEnd PrevNode;
  //Ссылка на родительский конечный узел дерева предыдущего уровня
  public readonly TreeNodeEnd Parent1;
  //Ссылка на родительский конечный узел дерева предыдущего уровня
  public readonly TreeNodeEnd Parent2;

  //Конструктор
  public TreeNodeEnd(byte[] pTermRef, TreeNodeEnd pParent1, TreeNodeEnd pParent2,
    TreeNodeEnd pPrevTreeNode = null)
  {
    pTermRef.CopyTo(Term = new byte[pTermRef.Length], 0);
    Parent1 = pParent1;
    Parent2 = pParent2;
    PrevNode = pPrevTreeNode;
  }

  //Очистка выделенных ресурсов - отсутствует
  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].Clear();
        Childs[i] = null;
      }
    }
  }
}


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

В пункте 1 происходит многократный попарный перебор терм с целью выявления возможности их склейки. Два терма склеиваются, если они отличаются друг от друга значениями только лишь в одной из позиций: у одного стоит ‘0’, а у другого – ‘1’. Склеивающиеся исходные (родительские) термы исключаются из дальнейшей работы, а вместо их двоих далее на следующей итерации п. 1 алгоритма рассматривается новая дочерняя терма, у которой на позиции различающихся переменных родительских терм стоит знак ‘*’. Таким образом, двоичный алфавит входных исходных терм внутри алгоритма расширяется до троичного: ‘0’, ‘1’, ‘*’. Следует отметить, что в данной реализации вместо массивов символов используются байтовые массивы, в которых символам ‘0’, ‘1’ и ‘*’ соответствуют значения байт 0, 1 и 2.

Пункт 1 в классе Quine_McCluskey реализован в процедуре LogicFuncMinimize двумя принципиально разными способами. Первый способ, основанный на 64 битных целочисленных хэш-кодах и поиске в .NET словаре Dictionary<UInt64,…>, работает при количестве входных переменных булевской функции меньше или равном 40, а второй, основанный на поиске в троичном дереве, включается при большем их количестве. Такое раздвоение обусловлено тем, что первый способ работает несколько быстрее, чем второй, поэтому его использование приоритетнее, но он работает корректно только при количестве входных переменных до 40, а при большем их количестве выходит за 64 бит разрядную сетку целочисленного хэш-кода, используемого для работы алгоритма. Действительно, т. к. в термах внутри алгоритма применяется троичная логика, то при количестве входных переменных равном 41 максимальное значение хэш-кода $3^{41}$ уже превышает максимальное значение ($2^{64}$-1), которое можно записать в 64 битную переменную.

Второй способ работы п. 1, работающий при количестве переменных во входных термах больше 40, основан на поисковом троичном дереве терм TreeFuncTerm. Промежуточные узлы дерева реализованы с помощью класса TreeNodeMiddle. Каждый из них может ссылаться максимум на три последующих узла в зависимости от того были ли в дерево добавлены соответствующие термы. Все конечные узлы являются экземплярами класса TreeNodeEnd, глубина до которых от корня у них всех одинакова и равна количеству входных переменных. Каждый конечный узел также имеет ссылку на другой узел TreeNodeEnd, который был добавлен до него, реализуя тем самым однонаправленный связанный список. Такого рода список используется для быстрого перебора всех конечный узлов поискового дерева в процессе их склеивания.

Если в п. 1 для терма не находится другого отличающегося от него только в одной позиции терма, т. е. терм ни с кем не склеивается, то он считается одним из результатов работы п. 1 алгоритма, исключается из дальнейшей работы в нём и поступает на вход пункта 2 работы алгоритма, реализованный в процедуре ReduceRedundancyTerms.

Отбрасывание избыточных терм в ReduceRedundancyTerms осуществляется с помощью алгоритма приближенного решения задачи о покрытии множества подмножествами переменной длины. Покрытие, близкое к кратчайшему даёт алгоритм преобразования таблицы покрытий (ТП), основанный на методе “минимальный столбец–максимальная строка”, который можно посмотреть, например здесь.

Приблизительная логика его работы состоит в следующем:

  1. Исходная таблица считается текущей преобразуемой ТП, множество строк покрытий – пусто;
  2. В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу;
  3. Если в таблице есть не вычеркнутые столбцы, то выполняется п. 2, иначе – покрытие построено.

Примечание: При подсчёте числа единиц в строке учитываются единицы в невычеркнуых столбцах.

Для проверки работы алгоритма используются две тестовые функции. Первая процедура позволяет для набора входных переменных количеством N сформировать совокупность терм количеством $2^N$, вычислить случайное значение ЛФ для каждого терма, провести минимизацию на основе тех термов, для которых соответствующее им значение функции было равно TRUE, и выгрузить их в случае необходимости в файл. После этого проводится проверка правильности работы минимизированной формы функции путём вычисления её значения для каждого терма и сравнения с исходным.

TestQuineMcCluskeyRandom (нажать для просмотра) 
public static void TestQuineMcCluskeyRandom(int iVariableAmount, string sFileName = "")
{
  int iTotalCombines = 1 << iVariableAmount;
  ICollection<KeyValuePair<byte[], bool>> FuncResult = new List<KeyValuePair<byte[], bool>>(iTotalCombines);
  if (!String.IsNullOrEmpty(sFileName)) File.Delete(sFileName);
  Random rnd = new Random();
  //int iLogicFuncMask = 0;
  //while (iLogicFuncMask == 0) iLogicFuncMask = rnd.Next(iTotalCombines);
  for (int iCounter = 0; iCounter < iTotalCombines; iCounter++)
  {
    int iCurValue = iCounter;
    byte[] pTerm = new byte[iVariableAmount];
    for (int i = 0; i < iVariableAmount; i++)
    {
      pTerm[i] = (byte)(iCurValue % 2);
      iCurValue /= 2;
    }
    bool bFuncValue = (rnd.Next(2) != 0);
    //bool bFuncValue = (iCounter & iLogicFuncMask) > 0;
    if (bFuncValue && !String.IsNullOrEmpty(sFileName))
    {
      File.AppendAllText(sFileName, pTerm.ToString() + Environment.NewLine);
    }
    FuncResult.Add(new KeyValuePair<byte[], bool>(pTerm, bFuncValue));
  }
  //Положительные термы
  IEnumerable<byte[]> pTrueTerms = FuncResult.Where(p => p.Value).Select(p => p.Key);
  //Запуск в работу
  DateTime DtStart = DateTime.Now;
  Console.WriteLine("Старт - " + DtStart.ToLongTimeString());
  Quine_McCluskey Logic = new Quine_McCluskey();
  Logic.Start(pTrueTerms);
  DateTime DtEnd = DateTime.Now;
  TimeSpan Elapsed = DtEnd - DtStart;
  Console.WriteLine("Завершение - " + DtEnd.ToLongTimeString());
  Console.WriteLine("Длительность - " + String.Format("{0:00}:{1:00}:{2:00}",
    Elapsed.Hours, Elapsed.Minutes, Elapsed.Seconds));
  //Сравнение результатов
  int iErrorsCounter = 0;
  foreach (KeyValuePair<byte[], bool> kvp in FuncResult)
  {
    if (Logic.Result.Calculate(kvp.Key) != kvp.Value) iErrorsCounter++;
  }
  Console.WriteLine("Кол-во входных переменных = " + iVariableAmount);
  Console.WriteLine("Кол-во входных термов = " + iTotalCombines);
  Console.WriteLine("Кол-во дизъюнктивных термов = " + Logic.Result.Terms.Count);
  Console.WriteLine("Кол-во ошибок = " + iErrorsCounter);
  Console.ReadLine();
}


Вторая тестовая процедура позволяет из файла загрузить наборы, записанные предыдущей тестовой функцией TestQuineMcCluskeyRandom, для которых булевская процедура должна принимать значения TRUE и провести проверку правильности работы минимизированной функции.

TestQuineMcCluskeyFile (нажать для просмотра) 
public static void TestQuineMcCluskeyFile(string sFileName, int iVariableAmount)
{
  int iTotalCombines = 1 << iVariableAmount;
  ICollection<KeyValuePair<string, bool>> FuncResult = new List<KeyValuePair<string, bool>>(iTotalCombines);
  string sFileContent = File.ReadAllText(sFileName);
  for (int iCounter = 0; iCounter < iTotalCombines; iCounter++)
  {
    int iCurValue = iCounter;
    string sLine = "";
    for (int i = 0; i < iVariableAmount; i++)
    {
      sLine += (iCurValue % 2).ToString();
      iCurValue /= 2;
    }
    bool bFuncValue = sFileContent.Contains(sLine + Environment.NewLine);
    FuncResult.Add(new KeyValuePair<string, bool>(sLine, bFuncValue));
  }
  //Запуск в работу
  DateTime DtStart = DateTime.Now;
  Console.WriteLine("Старт - " + DtStart.ToLongTimeString());
  Quine_McCluskey Logic = new Quine_McCluskey();
  Logic.Start(sFileName);
  DateTime DtEnd = DateTime.Now;
  TimeSpan Elapsed = DtEnd - DtStart;
  Console.WriteLine("Завершение - " + DtEnd.ToLongTimeString());
  Console.WriteLine("Длительность - " + String.Format("{0:00}:{1:00}:{2:00}",
    Elapsed.Hours, Elapsed.Minutes, Elapsed.Seconds));
  //Сравнение результатов
  int iErrorsCounter = 0;
  foreach (KeyValuePair<string, bool> kvp in FuncResult)
  {
    if (Logic.Result.Calculate(kvp.Key.ToArray()) != kvp.Value) iErrorsCounter++;
  }
  Console.WriteLine("Кол-во термов = " + Logic.Result.Terms.Count);
  Console.WriteLine("Кол-во ошибок = " + iErrorsCounter);
  Console.ReadLine();
}


При тестировании реализации алгоритма Мак-Класки выявлен её существенный недостаток, заключающийся в том, что при количестве входных переменных в термах более или равном 16 работа программы завершается в связи с нехваткой памяти в процедуре Skleivanie на строках:

X2Tree.Add(iCode, new TreeNodeEnd(x1.Value.Term, x1.Value, pSkleivNode, null));
X2Tree.AddTerm(x1.Term, x1, kvp.Value);

Причём эта проблема возникает при работе как по первому, так и по второму варианту работы пункта 1 соответственно порядку строк выше, которые кратко описаны в начале статьи.

Однако следует заметить, что проблема нехватки памяти возникает только в том случае, если оптимизирование происходит на наборе входных терм размером несколько меньше максимального количества $2^N$, где N – количество переменных. Если же используется сокращённый (неполный) набор с количеством Q < Qпор < $2^N$, то проблема не возникает до той поры, пока размер входного набора данных не перерастёт некоторый порог Qпор, критичный для алгоритма.

В качестве возможных путей преодоления этой проблемы исследовалась возможность определения TreeNodeEnd и TreeNodeMiddle не в виде классов языка C#, а в виде структур. Но в связи с принципиальным отличием между классами и структурами, состоящая в том, что нельзя получить ссылку на структуру, этот путь оказался тупиковым вследствие того, что исследуемая реализация в своей работе опирается именно на ссылки к TreeNodeEnd и TreeNodeMiddle.

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

Каких-либо иных возможностей на преодоление неприятностей с нехваткой памяти я не вижу. В связи с чем возникает вопрос можно ли что-то изменить, чтобы добиться стабильной работы алгоритма на полном наборе входных терм с количеством переменных хотя бы до 30? Или это врождённое свойство этого алгоритма, которое не поддаётся коррекции?

Тем не менее, несмотря на возможные проблемы с памятью, предложенная реализация алгоритма Мак-Класки в реальных задачах может быть использована в качестве достаточно быстрого и надёжного оптимизатора ЛФ, заданных набором терм своих входных переменных, при которых логическая функция принимает истинное значение, когда количество переменных N<16 или количество терм Q << $2^N$.
Tags:
Hubs:
+15
Comments8
4
Karma
0
Rating
Лобанов Сергей @Degun

Разработчик ПО

Send message

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr