Введение

Тип бинарной диаграммы решений

Диаграмма решений с подавлением нулей (ZSDD или ZDD) — это особый тип бинарной диаграммы решений (BDD) с фиксированным порядком переменных. Эта структура данных обеспечивает канонически компактное представление множеств, особенно подходящее для решения определенных комбинаторных задач. Вспомним стратегию редукции упорядоченной бинарной диаграммы решений (OBDD), то есть узел заменяется одним из его дочерних узлов, если оба исходящих ребра указывают на один и тот же узел. В отличие от этого, в ZDD узел заменяется его отрицательным дочерним узлом, если его положительное ребро указывает на терминальный узел 0. Это обеспечивает альтернативную строгую нормальную форму с улучшенным сжатием разреженных множеств. Она основана на правиле редукции, разработанном Синъити Минато в 1993 году.

Предыстория

На бинарной диаграмме решений булева функция может быть представлена как корневой, направленный, ациклический граф, состоящий из нескольких узлов принятия решений и терминальных узлов. В 1993 году Синъити Минато из Японии модифицировал BDD Рэндала Брайанта для решения комбинаторных задач. Его "Zero Suppressed" BDD (BDD с подавлением нулей) предназначены для представления и манипулирования разреженными множествами битовых векторов. Если данные для задачи представлены в виде битовых векторов длины n, то любое подмножество векторов может быть представлено булевой функцией от n переменных, возвращающей 1, когда вектор, соответствующий набору значений переменных, принадлежит множеству. Согласно Брайанту, можно использовать формы логических функций для представления задач, связанных с суммой произведений. Такие формы часто представляются в виде множеств "кубов", каждый из которых обозначается строкой, содержащей символы 0, 1 и «-». Например, функцию можно проиллюстрировать множеством {a, b, c}. Используя биты 10, 01 и 00 для обозначения символов 1, 0 и «-» соответственно, можно представить вышеуказанное множество битовыми векторами в форме {10, 01, 00}. Заметьте, что множество битовых векторов является разреженным, поскольку число векторов меньше 2<sup>n</sup>, что является максимальным числом битовых векторов, и множество содержит много нулевых элементов. В этом случае узел можно опустить, если присвоение переменной узла значения 1 приводит к тому, что функция возвращает 0. Это проявляется в том, что 1 в определенной битовой позиции означает, что вектор не принадлежит множеству. Для разреженных множеств это условие типично, и, следовательно, возможно исключить множество узлов. Минато доказал, что ZDD особенно подходят для комбинаторных задач, таких как классические задачи двухуровневой логической минимизации, задача тура рыцаря, моделирование отказов, анализ временных характеристик, задача N ферзей, а также слабое разбиение. Используя ZDD, можно уменьшить размер представления множества из n битовых векторов в OBDD максимум в n раз. На практике эта оптимизация статистически значима.

Особенности

Одной из особенностей ZDD является то, что их структура не зависит от количества входных переменных, при условии, что наборы комбинаций остаются одинаковыми. Нет необходимости заранее фиксировать количество входных переменных при построении графов. ZDD автоматически исключают переменные для объектов, которые никогда не встречаются в комбинациях, что обеспечивает эффективность при работе с разреженными комбинациями. Другим преимуществом ZDD является то, что количество путей, состоящих из единиц, в графе точно соответствует количеству элементов в наборе комбинаций. В исходных BDD устранение узлов нарушает это свойство. Поэтому ZDD лучше подходят для представления наборов комбинаций, чем простые BDD. Однако для представления обычных булевых функций предпочтительнее использовать исходные BDD, как показано на рисунке 7.

ZDD как словари

ZDD можно использовать для представления пятибуквенных слов английского языка, например, множества WORDS (размером 5757) из Stanford GraphBase. Один из способов сделать это – рассмотреть функцию, которая равна 1 тогда и только тогда, когда пять чисел , , , кодируют буквы английского слова, где , . Например, функция от 25 переменных имеет Z(f) = 6233 узлов – что не так уж плохо для представления 5757 слов. По сравнению с бинарными деревьями, триями или хеш-таблицами, ZDD может быть не лучшим выбором для выполнения простых поисков, но он эффективен при извлечении данных, которые указаны лишь частично, или данных, которые должны лишь приблизительно соответствовать ключу. Сложные запросы могут быть обработаны легко. Более того, ZDD требуют меньше переменных. Фактически, используя ZDD, можно представить эти пятибуквенные слова в виде разреженной функции, имеющей 26 × 5 = 130 переменных, где переменная, например, определяет, является ли вторая буква "a". Чтобы представить слово "crazy", можно установить F в true, когда и все остальные переменные равны 0. Таким образом, F можно рассматривать как семейство, состоящее из 5757 подмножеств и т.д. При использовании этих 130 переменных размер ZDD Z(F) составляет всего 5020 вместо 6233. По словам Кнута, эквивалентный размер B(F) при использовании BDD составляет 46 189 – значительно больше, чем Z(F). Несмотря на схожие теории и алгоритмы, ZDD значительно превосходят BDD при решении этой задачи. Следовательно, ZDD позволяют выполнять определенные запросы, которые слишком сложны для BDD. Сложные семейства подмножеств можно легко построить из элементарных семейств. Для поиска слов, содержащих определенный шаблон, можно использовать алгебру семейств на ZDD для вычисления , где P – шаблон, например .

Проблема с рыцарским туром

Проблема тура рыцаря имеет историческое значение. Граф рыцаря содержит n² вершин, представляющих поля шахматной доски. Рёбра графа иллюстрируют допустимые ходы рыцаря. Рыцарь должен посетить каждое поле доски ровно один раз. Олаф Шрёер, М. Лёббинг и Инго Вегенер подошли к решению этой задачи, рассматривая доску и присваивая булевы переменные каждому ребру графа, что в сумме составляет 156 переменных для обозначения всех рёбер. Решение задачи может быть представлено в виде 156-битного векторного сочетания. По словам Минато, построение ZDD для всех решений слишком велико для непосредственного решения. Более эффективно использовать принцип "разделяй и властвуй". Разделив задачу на две части доски и построив ZDD в подпространствах, можно решить проблему тура рыцаря, где каждое решение содержит 64 ребра. Однако, поскольку граф недостаточно разрежен, преимущество использования ZDD не столь очевидно.

Моделирование неисправностей

Н. Такахаси и др. предложили метод имитации неисправностей при наличии множественных дефектов с использованием OBDD. Этот дедуктивный метод распространяет наборы неисправностей от первичных входов к первичным выходам и выявляет неисправности на первичных выходах. Поскольку в этом методе используются выражения в виде униполярных кубических множеств, ZDD более эффективны. Оптимизации, достигаемые с помощью ZDD при вычислениях с униполярными кубическими множествами, указывают на то, что ZDD могут быть полезны при разработке САПР для ВЛСИ и в широком спектре других приложений.