Диаграмма принятия решений с подавлением нуля

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

Фон

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

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

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

Определения

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

1. Конечный узел – это либо:

Специальный узел ⊤, представляющий семейство единиц измерения. $\{\emptyset \}$ (т.е. пустое множество ), или
Специальный узел ⊥, представляющий пустое семейство. $\emptyset$ .

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

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

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

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

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

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

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

Мы называем Z нередуцированным ZDD, если ребро HI указывает на узел ⊥ или условие 4 не выполняется. В компьютерных программах логические функции могут быть выражены в битах, поэтому узел ⊤ и узел ⊥ могут быть представлены 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 представляет семейство

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

Ветвь LO можно представить как множества из F, не содержащие v : $F_{0}=\{\alpha :\alpha \in F,v\notin \alpha \}$

И ветвь HI — это множества в F, которые содержат v : $F_{1}=\{\alpha \smallsetminus \{v\}:\alpha \in F,v\in \alpha \}$

Пример

Рисунок 3
Рисунок 4
Рисунок 5
Рисунок 6

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

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

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

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

Функции

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

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

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

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

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

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

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

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

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

P\cup Q

)

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

P\cap Q

)

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

P-Q

)

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

\left\vert P\right\vert

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

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

Алгоритмы

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

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

 Getnode (top, P0, P1) {
   if (P1 == ø) return P0; /* node elimination */
   P = search a node with (top, P0, P1 ) in uniq-table; if (P exist) return P; /* node sharing */
   P = generate a node with (top, P0, P1 );
   append P to the uniq-table;
   return P; 
 }

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

 Subset1 (P, var) {
   if (P.top < var) return ø; 
   if (P.top == var) return P1; 
   if (P.top > var)
     return Getnode (P.top, Subset1(P0, var), Subset1(P1, var));
 }

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

 Change (P, var) {
   if (P.top < var) return Getnode (var, ø, P); 
   if (P.top == var) return Getnode (var, P1, P0);
   if (P.top > var)
     return Getnode (P.top, Change(P0, var), Change(P1, var));
 }

 Union (P, Q) {
   if (P == ø) return Q; 
   if (Q == ø) return P;
   if (P == Q) return P;
   if (P.top > Q.top) return Getnode (P.top, Union(P0, Q), P1);
   if (P.top < Q.top) return Getnode (Q.top, Union(P, Q0), Q1);
   if (P.top == Q.top) 
     return Getnode (P.top, Union(P0, Q0), Union(P1, Q1));
 }

 Intsec (P, Q) {
   if (P == ø) return ø; 
   if (Q == ø) return ø;
   if (P == Q) return P;
   if (P.top > Q.top) return Intsec(P0, Q);
   if (P.top < Q.top) return Intsec (P, Q0);
   if (P.top == Q.top) 
     return Getnode (P.top, Intsec(P0, Q0), Intsec(P1, Q1));
 }

 Diff (P, Q) {
   if (P == ø) return ø; 
   if (Q == ø) return P;
   if (P == Q) return ø;
   if (P.top > Q.top) return Getnode(P.top, Diff(P0, Q), P1;)
   if (P.top < Q.top) return Diff(P, Q0);
   if (P.top == Q.top) 
     return Getnode (P.top, Diff(P0, Q0), Diff(P1, Q1));
 }

 Count (P) {
   if (P == ø) return 0; 
   if (P == {ø}) return 1;
     return Count(P0) + Count(P1);
 }

Эти алгоритмы требуют экспоненциального времени для количества переменных в худшем случае; однако мы можем повысить производительность, используя кэш, который запоминает результаты последних операций аналогичным образом в BDD. Кэш предотвращает дублирование выполнения эквивалентных подграфов. Без каких-либо дубликатов алгоритмы могут работать за время, пропорциональное размеру графов, как показано на рисунках 9 и 10.

Приложение

ZDD как словари

ZDD можно использовать для представления пятибуквенных слов английского языка, , набора WORDS (размером 5757) из Stanford GraphBase например . Один из способов сделать это — рассмотреть функцию $f(x_{1},...,x_{25})$ определяется как 1 тогда и только тогда, когда пять чисел $(x_{1},...,x_{5})_{2}$ , $(x_{6},...,x_{10})_{2}$ , ..., $(x_{21},...,x_{25})_{2}$ закодировать буквы английского слова, где $a=(00001)_{2}$ , ..., $z=(11010)_{2}$ . Например, $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, можно представить эти пятибуквенные слова как разреженную функцию. $F(a_{1},...,z_{1},a_{2},...,z_{2},...,a_{5},...,z_{5})$ который имеет 26×5 = 130 переменных, где переменная $a_{2}$ например, определяет, является ли вторая буква «а». Чтобы представить слово «сумасшедший», можно сделать F истинным, когда $c_{1}=r_{2}=a_{3}=z_{4}=y_{5}=1$ а все остальные переменные равны 0. Таким образом, F можно рассматривать как семейство, состоящее из 5757 подмножеств. $\{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 для вычисления $(F/P)\sqcup P$ где P — шаблон, например $a_{1}\sqcup h_{3}\sqcup e_{5}$ .

ZDD для представления простых путей

Можно использовать ZDD для представления простых путей в неориентированном графе . Например, существует 12 способов пройти из левого верхнего угла сетки три на три (показано на рисунке 11) в правый нижний угол, не посещая ни одну точку дважды.

Рисунок 12: 12 возможных путей перехода от одного угла к другому диагональному углу.

Эти пути могут быть представлены ZDD, показанным на рисунке 13, в котором каждый узел mn представляет вопрос «включает ли путь дугу между m и n ?» Так, например, ветвь LO между 13 и 12 указывает на то, что если путь не включает в себя дугу от 1 до 3, следующее, что следует спросить, это включает ли он дугу от 1 до 2. Отсутствие уходящей ветви LO узел 12 указывает, что любой путь, который не идет от 1 к 3, должен идти от 1 к 2. (Следующий вопрос, который нужно задать, будет касаться дуги между 2 и 4.) В этом ZDD мы получаем первый путь на рисунке. 12, взяв ветви HI в узлах 13, 36, 68 и 89 ZDD (ветви LO, которые просто идут к ⊥, опущены). Хотя ZDD на рисунке 13 может показаться незначительным, преимущества ZDD становятся очевидными по мере увеличения сетки. Например, для сетки восемь на восемь число простых путей из угла в угол оказывается равным 789 360 053 252 (Кнут). Пути можно проиллюстрировать 33580 узлами с использованием ZDD.

Реальный пример простых путей был предложен Рэндалом Брайантом: «Предположим, я хочу совершить автомобильную поездку по континентальной части США, посетив все столицы штатов и проехав через каждый штат только один раз. Какой маршрут мне следует выбрать, чтобы свести к минимуму общее расстояние?" На рис. 14 показан неориентированный график этой дорожной карты, где числа указывают кратчайшие расстояния между соседними столицами. Проблема состоит в том, чтобы выбрать подмножество этих ребер, которые образуют гамильтонов путь наименьшей общей длины. Каждый гамильтонов путь в этом графе должен начинаться или заканчиваться в Огасте, штат Мэн (Мэн, штат Мэн). Предположим, вы начинаете в Калифорнии. Можно найти ZDD, характеризующее все пути от CA до ME. По словам Кнута, этот ZDD имеет всего 7850 узлов и фактически показывает, что возможны ровно 437 525 772 584 простых пути от CA до ME. По количеству ребер производящая функция равна

                       $4z^{11}+124z^{12}+1539z^{13}+...+33385461z^{46}+2707075z^{47}$ ;

поэтому самые длинные такие пути являются гамильтоновыми и имеют размер 2 707 075. ZDD в этом случае эффективны для простых путей и гамильтоновых путей .

Проблема восьми ферзей

Определите 64 входные переменные для представления клеток на шахматной доске. Каждая переменная обозначает наличие или отсутствие ферзя на этом поле. Учтите это,

В определенном столбце только одна переменная равна «1».
В конкретной строке только одна переменная равна «1».
На определенной диагональной линии одна переменная или ни одна переменная не равна «1».

Хотя эту проблему можно решить путем создания OBDD, более эффективно использовать ZDD. Построение ZDD для задачи 8 ферзей требует 8 шагов от S1 до S8. Каждый шаг можно определить следующим образом:

S1: представляет все варианты размещения ферзя в первом ряду.

S2: представляет все варианты размещения ферзя во втором ряду, чтобы не нарушать первый ферзь.

S3: представляет все варианты размещения ферзя в третьем ряду, чтобы он не нарушал предыдущие ферзи.

…

S8: представляет все варианты размещения ферзя в восьмом ряду, чтобы не нарушать предыдущие ферзи.

ZDD для S8 состоит из всех потенциальных решений проблемы 8 ферзей. Для этой конкретной проблемы кэширование может значительно улучшить производительность алгоритма. Использование кэша во избежание дублирования может решить проблемы N-Queens до 4,5 раз быстрее, чем использование только базовых операций (как определено выше), как показано на рисунке 10.

Задача о рыцарском путешествии

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

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

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

Доступные пакеты

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

Ссылки

Дальнейшее чтение

Минато, Син-Ичи (1993). «BDDS с подавлением нуля для манипуляций с множествами в комбинаторных задачах». Материалы 30-й международной конференции по автоматизации проектирования - DAC '93 . стр. 272–277. дои : 10.1145/157485.164890 . ISBN 978-0-89791-577-9 . S2CID 11096308 .
Ч. Мейнель, Т. Теобальд, « Алгоритмы и структуры данных в проектировании СБИС: OBDD – основы и приложения» , Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1998.
Минато, Синъити (май 2001 г.). «BDD с нулевым подавлением и их приложения». Международный журнал по программным инструментам для трансфера технологий . 3 (2): 156–170. дои : 10.1007/s100090100038 . hdl : 2115/16895 . S2CID 42919336 .
Брайант, Р.Э. (1995). «Бинарные диаграммы решений и не только: технологии формальной проверки». Материалы Международной конференции IEEE по компьютерному проектированию (ICCAD) . стр. 236–243. дои : 10.1109/ICCAD.1995.480018 . ISBN 978-0-8186-7213-2 . S2CID 62602492 .
Линн, Бен. «ЗДД». ZDD – Введение, Стэнфордский университет, 2005 г., crypto.stanford.edu/pbc/notes/zdd/.
Мищенко, Алан (2001). «Введение в двоичные диаграммы решений с подавлением нуля». CiteSeerX 10.1.1.67.8986 .
Кнут, Дональд Э. Искусство компьютерного программирования, Том 4. 22 декабря 2008 г.

Внешние ссылки

Линн, Бен. «ЗДД». ZDD – Введение, Стэнфордский университет, 2005 г., crypto.stanford.edu/pbc/notes/zdd/
Дональд Кнут , Забавы с двоичными диаграммами решений с нулевым подавлением (ZDD) (видеолекция, 2008 г.)
Минато Синъити , Подсчет путей в графах (основы ZDD) (видеоиллюстрация, созданная на Miraikan)