Диаграмма решения с нулевым подавлением - Zero-suppressed decision diagram

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

Фон

В Диаграмма двоичного решения, а Логическая функция можно представить как укорененный, направленный, ациклический граф, который состоит из нескольких узлов принятия решений и конечных узлов. В 1993 году Син-ичи Минато из Японии модифицировал Рэндал Брайант BDD для решения комбинаторные задачи. Его диски BDD с нулевым подавлением направлены на представление и манипулирование разреженные наборы битовых векторов. Если данные для задачи представлены в виде битовых векторов длины n, то любое подмножество векторов может быть представлено логической функцией по n переменным, дающей 1, когда вектор, соответствующий присвоению переменной, находится в наборе.

По словам Брайанта, можно использовать формы логические функции для выражения проблем, связанных с суммой произведений. Такие формы часто представляют как наборы «кубиков», каждый из которых обозначается строкой, содержащей символы 0, 1 и -. Например, функция ${displaystyle ({ar {x}} _ {1} land x_ {2}) lor ({ar {x}} _ {2} igoplus x_ {3})}$ можно проиллюстрировать набором ${displaystyle {01 -, - 11, -00}}$ . Используя биты 10, 01 и 00 для обозначения символов 1, 0 и - соответственно, можно представить вышеупомянутый набор с битовыми векторами в виде ${displaystyle {011000,001010,000101}}$ . Обратите внимание, что набор битовых векторов разрежен в том смысле, что количество векторов меньше 2^п, который является максимальным количеством битовых векторов, и набор содержит много элементов, равных нулю. В этом случае узел может быть опущен, если установка переменной узла в 1 приводит к тому, что функция возвращает 0. Это видно в том условии, что 1 в некоторой битовой позиции означает, что вектор не входит в набор. Для разреженных наборов это обычное условие, и, следовательно, возможно исключение многих узлов.

Минато доказал, что ZDD особенно подходят для комбинаторные задачи, такие как классические задачи в двухуровневая логическая минимизация, задача рыцарского тура, моделирование неисправностей, временной анализ, проблема N ферзей, а также слабое деление. Используя ZDD, можно уменьшить размер представления набора n-битовых векторов в OBDD не более чем в n раз. На практике оптимизация статистически значимый.

Определения

Мы определяем диаграмму принятия решений с нулевым подавлением (ZDD) как любой ориентированный ациклический граф, такой что:

1. А конечный узел либо:

Специальный узел ⊤ (ИСТИННЫЙ узел), или:
Специальный узел ⊥ (узел FALSE).

2. Каждый нетерминальный узел удовлетворяет следующим условиям:

а. Узел помечен положительным целым числом v. Эта метка не обязательно должна быть уникальной.

б. Узел имеет степень выхода 2. Одно из исходящих ребер называется «LO», а другое - «HI». (На диаграммах можно нарисовать пунктирные линии для краев LO и сплошные линии для краев HI)

c. Узел назначения либо конечный, либо помечен целым числом, строго большим, чем v. Таким образом, на диаграммах можно опустить стрелки, потому что направления краев могут быть выведены из меток.

d. Ребро HI никогда не указывает на узел ⊥.

3. Есть ровно один узел с нулевой внутренней степенью - корневой узел. Корневой узел либо конечный, либо обозначен наименьшим целым числом на диаграмме.

4. Если два узла имеют одинаковую метку, то их края LO или HI указывают на разные узлы. Другими словами, нет никаких избыточных узлов.

Мы называем Z нередуцированным ZDD, если ребро HI указывает на узел или условие 4 не выполняется.

Рисунок 1 и Рисунок 2: Удаление узла ZDD и совместное использование узла

В компьютерных программах логические функции могут быть выражены в битах, поэтому узел ⊤ и узел могут быть представлены как 1 и 0. Исходя из приведенного выше определения, мы можем эффективно представлять наборы комбинаций, применяя два правила к BDD:

1.Удалите все узлы, 1-ребро которых указывает на 0-концевой узел. Затем соедините край с другим подграфом напрямую, как показано на рисунке 1.

2. Поделитесь всеми эквивалентными подграфами так же, как и для оригинальных BDD.

Если количество и порядок входных переменных фиксированы, BDD с подавлением нуля представляет булеву функцию однозначно (как показано на рисунке 2, можно использовать BDD для представления булевого двоичного дерева).

Представление семейства множеств

Пусть F - ZDD. Пусть v будет его корневым узлом. Потом:

1. Если v = ⊥, то других узлов быть не может, а F представляет Ø, пустое семейство.

2. Если v = ⊤, то других узлов быть не может, а F представляет семейство, содержащее только пустое множество {Ø}. Мы называем это единичным семейством и обозначаем его.

3. Если у v двое детей. Пусть v0 - узел LO, а v1 - узел HI. Пусть Fi - семейство, представленное ZDD с корнем в vi, что можно показать с помощью доказательства индукции. Тогда F представляет семейство

{displaystyle F_ {0} cup {alpha cup {v} mid alpha in F_ {1}}}

Можно представить ветвь LO как множества в F, которые не содержат v: ${displaystyle F_ {0} = {alpha: alpha на F, votin alpha}}$

И ветвь HI как множества в F, которые действительно содержат v: ${displaystyle F_ {1} = {alpha ackslash {v}: alpha in F, vin alpha}}$

Рисунок 3: Элементарное семейство в ZDD

Рисунок 4:

{displaystyle {emptyset} чашка {emptyset чашка {2}} = {emptyset, {2}}}

Пример

Фигура 5:

{displaystyle {{2}} cup {emptyset cup {1}} = {{1}, {2}}}

Рисунок 6:

{displaystyle {{1} чашка {2}} = {{1,2}}}

Рисунок 3: Семья ${displaystyle emptyset cup {emptyset cup {2}} = {{2}}}$ . Мы можем назвать это ${displaystyle e_ {2}}$ , элементарная семья. Элементарные семьи состоят из формы ${displaystyle {{n}}}$ , и обозначаются ${displaystyle e_ {n}}$ .

Рисунок 4: Семья ${displaystyle {emptyset} cup {emptyset cup {2}} = {emptyset, {2}}}$

Рисунок 5: Семья ${displaystyle {{2}} cup {emptyset cup {1}} = {{1}, {2}}}$

Рисунок 6: Семья ${displaystyle {{1} чашка {2}} = {{1,2}}}$

Функции

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

Рисунок 7: Битовые манипуляции и основные операции. Рисунок 8: Подавление нерелевантных переменных

Основные операции

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

Empty () возвращает ø (пустой набор)

Base () возвращает {0}

Subset1 (P, var) возвращает подмножество P, например вар = 1

Subset0 (P, var) возвращает подмножество P, например вар = 0

Change (P, var) возвращает P, когда вар перевернут

Union (P, Q) возвращает (

{displaystyle Pcup Q}

)

Intsec (P, Q) возвращает (

{displaystyle Pcap Q}

)

Diff (P, Q) возвращает (

{displaystyle P-Q}

)

Count (P) возвращает

{displaystyle leftvert Pightvert}

. (количество элементов)

В ZDD нет операции NOT, которая является важной операцией в оригинальных BDD. Причина в том, что дополнительный набор ${displaystyle {ar {P}}}$ невозможно вычислить без определения универсального множества ${displaystyle U}$ . В ZDDs, ${displaystyle {ar {P}}}$ можно вычислить как Diff (U, P).

Алгоритмы

Предполагать ${displaystyle leftvert Pightvert = leftvert P_ {0} ightvert + leftvert P_ {1} ightvert}$ , мы можем рекурсивно вычислить количество наборов в ZDD, что позволяет нам получить 34-й набор из 54 членов семьи. Произвольный доступ выполняется быстро, и любая операция, возможная для массива наборов, может быть эффективно выполнена на ZDD.

По словам Минато, вышеупомянутые операции для ZDD могут выполняться рекурсивно, как и оригинальные BDD. Чтобы просто описать алгоритмы, определим процедуру Getnode (вверху, P0, P1) который возвращает узел для переменной top и два подграфа P0 и P1. Мы можем использовать хеш-таблицу, называемую uniq-table, чтобы каждый узел оставался уникальным. Исключение узлов и их совместное использование осуществляется только Getnode ().

 Getnode (top, P0, P1) {if (P1 == ø) return P0; / * исключение узла * / P = поиск узла с (top, P0, P1) в uniq-таблице; если (P существует) вернуть P; / * совместное использование узла * / P = генерировать узел с помощью (top, P0, P1); добавить P в uniq-таблицу; return P; }

С помощью Getnode (), затем мы можем представить другие основные операции следующим образом:

 Subset1 (P, var) {если (P.top  var) return Getnode (P.top, Subset1 (P0, var), Subset1 (P1, var)); }

 Subset0 (P, var) {if (P.top  var) return Getnode (P.top, Subset0 (P0, var), Subset0 (P1, var)); }

 Изменить (P, var) {if (P.top  var) return Getnode (P.top, Change (P0, var), Change (P1, var)); } Union (P, Q) {if (P == ø) return Q; если (Q == ø) вернуть P; если (P == Q) вернуть P; если (P.top> Q.top) вернуть Getnode (P.top, Union (P0, Q), P1); если (P.top  Intsec (P, Q) {если (P == ø) вернуть ø; if (Q == ø) return ø; если (P == Q) вернуть P; если (P.top> Q.top) return Intsec (P0, Q); если (P.top  Diff (P, Q) {if (P == ø) return ø; если (Q == ø) вернуть P; if (P == Q) return ø; if (P.top> Q.top) return Getnode (P.top, Diff (P0, Q), P1;) if (P.top  Count (P) {if (P == ø) возврат 0; если (P == {ø}) вернуть 1; вернуть счетчик (P0) + счетчик (P1); }
Эти алгоритмы в худшем случае занимают экспоненциальное время для числа переменных; однако мы можем улучшить производительность, используя кэш, который запоминает результаты недавних операций аналогичным образом в BDD. Кэш предотвращает дублирование выполнения для эквивалентных подграфов. Без каких-либо дубликатов алгоритмы могут работать за время, пропорциональное размеру графиков, как показано на рисунках 9 и 10.
  Рисунок 9: Результаты в задаче N-Queens Рисунок 10: Производительность ZDD по сравнению с производительностью BDD
Заявление









ZDD как словари
ZDD могут использоваться для представления пятибуквенных слов английского языка, набора СЛОВ (размера 5757) из Стэнфордский GraphBase например. Один из способов сделать это - рассмотреть функцию  ${displaystyle f (x_ {1}, ..., x_ {25})}$  который определяется как 1 тогда и только тогда, когда пять чисел  ${displaystyle (x_ {1}, ..., x_ {5}) _ {2}}$ ,  ${displaystyle (x_ {6}, ..., x_ {10}) _ {2}}$ , ...,  ${displaystyle (x_ {21}, ..., x_ {25}) _ {2}}$  закодировать буквы английского слова, где  ${displaystyle a = (00001) _ {2}}$ , ...,  ${displaystyle z = (11010) _ {2}}$ . Например, ${displaystyle f (0,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0, 0, x_ {25}) = x_ {25}}$ . Функция 25 переменных имеет Z (f) = 6233 узла, что неплохо для представления 5757 слов. бинарные деревья, пытается, или же хеш-таблицы, ZDD может быть не лучшим вариантом для выполнения простого поиска, но он эффективен при извлечении данных, которые указаны только частично, или данных, которые должны соответствовать ключу только приблизительно. Сложные запросы можно легко обрабатывать. Более того, ZDD не включают столько переменных. Фактически, используя ZDD, можно представить эти пятибуквенные слова как разреженную функцию  ${displaystyle F (a_ {1}, ..., z_ {1}, a_ {2}, ..., z_ {2}, ..., a_ {5}, ..., z_ {5}) }$ который имеет 26 × 5 = 130 переменных, где переменная  ${displaystyle a_ {2}}$  например, определяет, является ли вторая буква «а». Чтобы представить слово «сумасшедший», можно сделать F истинным, когда  ${displaystyle c_ {1} = r_ {2} = a_ {3} = z_ {4} = y_ {5} = 1}$  а все остальные переменные равны 0. Таким образом, F можно рассматривать как семейство, состоящее из 5757 подмножеств  ${displaystyle {w_ {1}, h_ {2}, i_ {3}, c_ {4}, h_ {5}}}$ и т.д. С этими 130 переменными размер ZDD Z (F) фактически равен 5020 вместо 6233. Согласно Кнуту, эквивалентный размер B (F) с использованием BDD составляет 46 189, что значительно больше, чем Z (F). Несмотря на наличие схожих теорий и алгоритмов, ZDD превосходят BDD по этой проблеме с довольно большим отрывом. Следовательно, ZDD позволяют нам выполнять определенные запросы, которые слишком обременительны для BDD. Комплексные семейства подмножеств легко построить из элементарных семейств. Для поиска слов, содержащих определенный образец, можно использовать семейную алгебру на ZDD для вычисления  ${displaystyle (F / P) sqcup P}$  где P - шаблон, например  ${displaystyle a_ {1} sqcup h_ {3} sqcup e_ {5}}$ .
  Рисунок 11: сетка три на три
ZDD для представления простых путей
Можно использовать ZDD для представления простые пути в неориентированный граф. Например, есть 12 способов перейти из верхнего левого угла сетки три на три (показанной на рисунке 11) в нижний правый угол, не посещая какую-либо точку дважды.
  Рисунок 12: 12 возможных путей перехода от одного угла к другому диагональному углу
Эти пути могут быть представлены ZDD, показанным на рисунке 13. В этом ZDD мы получаем первый путь, взяв ветви HI в узле 13, узле 36, узле 68 и узле 89 ZDD (ветви LO, которые просто переходят к ⊥ опущены). Хотя ZDD на рисунке 13 может показаться несущественным, преимущества ZDD становятся очевидными по мере увеличения размера сетки. Например, для сетки восемь на восемь количество простых путей от угла до угла оказывается равным 789, 360 053 252 (Кнут). Пути могут быть проиллюстрированы 33580 узлами с использованием ZDD.
  Рисунок 13: ZDD для простых путей сетки три на три
Пример из реальной жизни простых путей был предложен Рэндалом Брайантом: «Предположим, я хочу совершить автомобильную поездку по континентальной части США, посетив все столицы штатов и проехав через каждый штат только один раз. Какой маршрут мне выбрать, чтобы минимизировать общее расстояние? » На рисунке 14 показан неориентированный граф для этой дорожной карты, числа которого указывают кратчайшие расстояния между соседними столицами. Проблема состоит в том, чтобы выбрать подмножество этих ребер, которые образуют Гамильтонов путь наименьшей общей длины. Каждый Гамильтонов путь на этом графике должно либо начинаться, либо заканчиваться в Огасте, штат Мэн (Мэн). Предположим, кто-то начинает в CA. Можно найти ZDD, который характеризует все пути от CA до ME. По словам Кнута, этот ZDD имеет только 7850 узлов и фактически показывает, что возможны ровно 437 525 772 584 простых пути от CA к ME. По количеству ребер производящая функция равна 
                       ${displaystyle 4z ^ {11} + 124z ^ {12} + 1539z ^ {13} + ... + 33385461z ^ {46} + 2707075z ^ {47}}$ ;
поэтому самые длинные такие пути являются гамильтоновыми, их размер составляет 2 707 075. ZDD в этом случае эффективны для простых путей и Гамильтоновы пути.
  Рисунок 14: Ненаправленный граф континентальных штатов США
проблема восьми ферзей
Задайте 64 входных переменных для представления квадратов на шахматной доске. Каждая переменная обозначает наличие или отсутствие ферзя на этом поле. Считают, что, 
В конкретном столбце только одна переменная - «1».
В отдельной строке только одна переменная - «1».
На определенной диагональной линии одна или никакая переменная равна «1».
Хотя эту проблему можно решить, построив OBDD, более эффективно использовать ZDD. Построение ZDD для задачи 8 ферзей требует 8 шагов от S1 до S8. Каждый шаг можно определить следующим образом:
S1: представляет все варианты размещения ферзя в первом ряду.
S2: Представляет все варианты размещения ферзя во втором ряду, чтобы не нарушить положение первого ферзя.
S3: Представляет все варианты размещения ферзя в третьем ряду, чтобы не нарушать предыдущие ферзя.
…
S8: Представляет все варианты размещения ферзя в восьмом ряду, чтобы он не нарушал предыдущие ферзя.
ZDD для S8 состоит из всех возможных решений проблемы 8-ферзей. Для этой конкретной проблемы кэширование может значительно улучшить производительность алгоритма. Использование кеша для предотвращения дублирования может улучшить проблемы N-Queens до 4,5 раз быстрее, чем использование только базовых операций (как определено выше), показанных на рисунке 10.
Проблема рыцарского тура
Проблема рыцарского тура имеет историческое значение. Граф коня содержит n2 вершины, изображающие клетки шахматной доски. Ребра показывают допустимые ходы коня. Конь может посетить каждую клетку доски ровно один раз. Олаф Шреер, М. Лёббинг и Инго Вегенер подошли к этой проблеме, а именно на доске, назначив булевы переменные для каждого ребра на графе, в общей сложности 156 переменных для обозначения всех ребер. Решение проблемы может быть выражено 156-битным комбинированным вектором. По словам Минато, создание ZDD для всех решений слишком велико, чтобы решать его напрямую. Легче разделять и побеждать. Разделив задачи на две части доски и построив ZDD в подпространствах, можно решить задачу конного тура с каждым решением, содержащим 64 ребра. Однако, поскольку график не очень разреженный, преимущество использования ZDD не так очевидно. 
Моделирование неисправностей
Н. Такахаши и др. Предложили метод моделирования неисправностей при множественных неисправностях с использованием OBDD. Этот дедуктивный метод передает наборы неисправностей с первичных входов на первичные выходы и фиксирует неисправности на первичных выходах. Поскольку в этом методе используются выражения unate cube set, ZDD более эффективны. Оптимизация ZDD в вычислениях unate cube set показывает, что ZDD могут быть полезны при разработке систем САПР VLSI и множества других приложений.
Смотрите также









Диаграмма упорядоченных двоичных решений (OBDD)
Схема принятия решения о перестановке (πDD)
Схема принятия решения о последовательности (SeqDD)
Диаграмма принятия решений (SDD)
Диаграмма групповых решений (GDD)
Доступные пакеты









CUDD: Пакет BDD, написанный на C, который реализует BDD и ZBDD, Университет Колорадо, Боулдер.
JDD, Java-библиотека, реализующая общие операции BDD и ZBDD.
Графиллион, Программная реализация ZDD на основе Python
[1], Реализация CWEB ZDD Дональда Кнута.
Рекомендации









Син-ичи Минато "BDD с нулевым подавлением для управления множеством в комбинаторных задачах ", DAC '93: Материалы 30-й международной конференции по автоматизации проектирования, 1993 г.
Гл. Майнель, Т. Теобальд "Алгоритмы и структуры данных в VLSI-дизайне: OBDD - основы и приложения », Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1998.
Минато, Син-ичи. «Диски BDD с нулевым подавлением и их приложения». https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf, Университет Хоккайдо, май 2001 г., https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf.
Минато, Син-ичи. «BDD с нулевым подавлением для манипулирования множеством в комбинаторных задачах». 1993 г., DOI:https://pdfs.semanticscholar.org/9593/6223362a16a50de2959475d87aefe2a1fec7.pdf.
Брайант, Рэндал Э. «Двоичные диаграммы принятия решений и не только: технологии, способствующие формальной проверке». http://Repository.cmu.edu/Cgi/Viewcontent.cgi?Article=1245&Context=Compsci, Университет Карнеги-Меллона, ноябрь 1995 г., repository.cmu.edu/cgi/viewcontent.cgi?article=1245&context=compsci.
Линн, Бен. «ZDDs». ZDDs - Введение, Стэнфордский университет, 2005 г., crypto.stanford.edu/pbc/notes/zdd/.
Мищенко Алан. «Введение в двоичные диаграммы решений с нулевым подавлением». 5 февраля 2014 г., doi:https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf.
Кнут, Дональд Э. Искусство программирования, Том 4. 22 декабря 2008 г.
внешняя ссылка









Минато, Син-ичи. «Диски BDD с нулевым подавлением и их приложения». https://Www.researchgate.net/Profile/Shin-ichi_Minato/Publication/37555760_Zero-suppressed_BDDs_and_their_applications/Links/02e7e52b85cd639cb5000000.Pdf, Университет Хоккайдо, май 2001 г., www.researchgate.net/profile/Shin-ichi_Minato/publication/37555760_Zero-suppressed_BDDs_and_their_applications/links/02e7e52b85cd639cb5000000.pdf.
Минато, Син-ичи. «BDD с нулевым подавлением для манипулирования множеством в комбинаторных задачах». 1993 г., DOI:https://pdfs.semanticscholar.org/9593/6223362a16a50de2959475d87aefe2a1fec7.pdf.
Брайант, Рэндал Э. «Двоичные диаграммы принятия решений и за их пределами: технологии, способствующие формальной проверке». http://Repository.cmu.edu/Cgi/Viewcontent.cgi?Article=1245&Context=Compsci, Университет Карнеги-Меллона, ноябрь 1995 г., repository.cmu.edu/cgi/viewcontent.cgi?article=1245&context=compsci.
Линн, Бен. «ZDDs». ZDDs - Введение, Стэнфордский университет, 2005 г., crypto.stanford.edu/pbc/notes/zdd/.
Алан Мищенко, Алан. «Введение в двоичные диаграммы решений с нулевым подавлением». 5 февраля 2014 г., doi:https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf.
Алан Мищенко, Введение в двоичные диаграммы принятия решений с нулевым подавлением
Дональд Кнут, Развлечение с двоичными диаграммами решений с нулевым подавлением (ZDD) (видеолекция, 2008 г.)
Минато Син-ичи, Подсчет путей в графах (основы ZDD) (видеоиллюстрация, созданная на Мираикане)