Бинарная диаграмма решений

Бинарная диаграмма решений (БДР) или программа с ветвлением является формой представления булевой функции <math>f(x_1, x_2, ..., x_n)</math> от <math>n</math> переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных <math>x_i</math>), каждый из которых имеет по два потомка, и двух терминальных узлов (помеченных 0 и 1), каждый из которых соответствует одному из двух значений булевой функции. В зарубежной литературе бинарные диаграммы решений и программы с ветвлением называются binary decision diagram (BDD) и branching programs (BP) соответственно.

Определение

Булеву функцию <math>f(x_1, x_2, ..., x_n)</math> можно представить в виде направленного ациклического графа, состоящего из нескольких внутренних узлов решений и двух терминальных узлов, называемых 0-терминальный узел и 1-терминальный узел. Каждый внутренний узел решений на уровне <math>i</math> помечен булевой переменной <math>x_i</math> и имеет по два потомка, называемых младшим потомком и старшим потомком. Переход от внутренного узла <math>x_i</math> к младшему или старшему потомку выполняется в зависимости от значения переменной <math>x_i</math> (0 или 1 соответственно). Для заданных значений <math>x_1, x_2, ..., x_n</math> путь от корневого узла до 1-терминального узла соответствуют тому, что на этих входных значениях булева функция <math>f(x_1, x_2, ..., x_n)</math> принимает значение 1.

БДР называется упорядоченной, если различные переменные появляются в том же порядке на всем пути от корневого узла графа. БДР называется сокращенной, если для графа применены следующие два правила сокращения:

• Слияние любых изоморфных подграфов.
• Удаление всех узлов с изоморфными потомками.

В большинстве случаев под бинарной диаграммой решений понимают именно сокращенную упорядоченную бинарную диаграмму решений (СУБДР). Преимущество сокращенной упорядоченной БДР в том, что она является канонической (уникальной) для конкретной функции и заданного порядка переменных. Это свойство делает СУБДР полезной для проверки функциональной эквивалентности.

Пример

На рисунке слева изображено бинарное дерево принятия решений (без применения правил сокращения), соответствующее приведенной на этом же рисунке таблице истинности для булевой функции <math>f(x_1, x_2, x_3)</math>. Для заданных входных значений <math>x_1</math>, <math>x_2</math>, <math>x_3</math> можно определить значение булевой функции, двигаясь по дереву от корневого узла дерева к терминальным узлам, выбирая направление перехода из узла <math>x_i</math> в зависимости от входного значения <math>x_i</math>. Пунктирными линиями на рисунке изображены переходы к младшему потомку, а непрерывными линиями изображены переходы к старшему потомку. Например, если заданы входные значения (<math>x_1 = 0</math>, <math>x_2 = 1</math>, <math>x_3 = 1</math>), то из корневого узла <math>x_1</math> необходимо перейти по пунктирной линии влево (так как значение <math>x_1</math> равно 0), после этого необходимо перейти по непрерывным линиям вправо (так как значения <math>x_2</math> и <math>x_3</math> равны 1). В результате мы окажемся в 1-терминальном узле, то есть значение <math>f(x_1 = 0, x_2 = 1, x_3 = 1)</math> равно 1.

Бинарное дерево принятия решений на рисунке слева можно преобразовать в бинарную диаграмму решений путём применения двух правил сокращения. Результирующая БДР изображена на рисунке справа.

История

Основной идеей для создания такой структуры данных послужило разложение Шеннона. Любую булеву функцию по одной из входных переменных можно разделить на две подфункции, называемых положительным и отрицательным дополнением, из которых по принципу if-then-else выбирается только одна подфункция в зависимости от значения входной переменной (по которой выполнялось разложение Шеннона). Представляя каждую такую подфункцию в виде поддерева и продолжая разложение по оставшимся входным переменным, можно получить дерево принятия решений, сокращение которого даст бинарную диаграмму решений. Информация об использовании бинарных диаграмм решений или бинарных ветвящихся программ была впервые опубликована в 1959 году в техническом журнале «Bell Systems Technical Journal»

Потенциал для создания эффективных алгоритмов, основанных на использовании этой структуры данных, исследовал Randal Bryant из университета Карнеги — Меллон: его подход заключался в использовании фиксированного порядка переменных (для однозначности канонического представления каждой булевой функции) и повторного использования общих подграфов (для компактности). Применение этих двух ключевых концепций позволяет повысить эффективность структур данных и алгоритмов для представления множеств и отношений между ними. Использование несколькими БДР общих подграфов привело к появлению такой структуры данных, как разделяемая сокращенная упорядоченная бинарная диаграмма решений (Shared Reduced Ordered Binary Decision Diagram). Название БДР теперь в основном используется для этой конкретной структуры данных.

Дональд Кнут в своей видеолекции [myvideos.stanford.edu/player/slplayer.aspx?coll=ea60314a-53b3-4be2-8552-dcf190ca0c0b&co=18bcd3a8-965a-4a63-a516-a1ad74af1119&o=true Fun With Binary Decision Diagrams (BDDs)] назвал бинарные диаграммы решений «одной из действительно фундаментальных структур данных, которые появились за последние двадцать пять лет» и отметил, что публикация Randal Bryant от 1986 года, осветившая использование бинарных диаграмм решений для манипуляции над булевыми функциями, являлась некоторое время наиболее цитируемой публикацией в компьютерной науке.

Применение

БДР широко используются в системах автоматизированного проектирования (САПР) для синтеза логических схем и в формальной верификации.

В электронике каждая конкретная БДР (даже не сокращенная и не упорядоченная) может быть непосредственно реализована заменой каждого узла на мультиплексор с двумя входами и одним выходом.

Порядок переменных

Размер БДР определяется как булевой функцией, так и выбором порядка входных переменных. При составлении графа для булевой функции <math>f(x_1,\ldots, x_{n})</math> количество узлов в лучшем случае может линейно зависеть от <math>n</math>, а в худшем случае зависимость может быть экспоненциальной при неудачном выборе порядка входных переменных. Например, дана булева функция <math>f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}.</math> Если использовать порядок переменных <math>x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}</math>, то понадобится 2ⁿ⁺¹ узлов для представления функции в виде БДР. Иллюстрирующая БДР для функции от 8 переменных изображена на рисунке слева. А если использовать порядок <math>x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}</math>, то можно получить эквивалентную БДР из 2n+2 узлов. Иллюстрирующая БДР для функции от 8 переменных изображена на рисунке справа.

Выбор порядка переменных является критически важным при использовании таких структур данных на практике. Проблема нахождения лучшего порядка переменных является NP-полной задачей. Более того, NP-полной является даже задача нахождения субоптимального порядка переменных, при котором для любой константы c > 1 размер БДР не более чем в c раз больше оптимального. Однако существуют эффективные эвристические методы для решения этой проблемы.

Кроме того, существуют такие функции, для которых размер графа всегда растет экспоненциально с ростом числа переменных, независимо от порядка переменных. Это относится к функциям умножения, что указывает на явную сложность факторизации.

Исследования бинарных диаграмм решений привели к появлению множества смежных видов графов, таких, как BMD (Binary Moment Diagrams), ZDD (Zero Suppressed Decision Diagram), FDD (Free Binary Decision Diagrams), PDD (Parity decision Diagrams), и MTBDDs (Multiple terminal BDDs).

Логические операции над бинарными диаграммами решений

Многие логические операции (конъюнкция, дизъюнкция, отрицание) могут быть выполнены непосредственно над БДР с помощью алгоритмов, выполняющих манипуляции над графами за полиномиальное время. Однако повторение этих операций множество раз, например, при формировании конъюнкций или дизъюнкций набора БДР, могут привести к экспоненциально большой БДР в худшем случае. Это происходит из-за того, что результатом любых предшествующих операций над двумя БДР в общем случае может быть БДР с размером, пропорциональным произведению предшествующих размеров, поэтому для нескольких БДР размер может увеличиваться экспоненциально.

См. также

• Задача выполнимости булевых формул
• Булева алгебра

Примечания

• R. Ubar, «Test Generation for Digital Circuits Using Alternative Graphs (in Russian)», in Proc. Tallinn Technical University, 1976, No.409, Tallinn Technical University, Tallinn, Estonia, pp. 75–81.

Рекомендуемая литература

• D. E. Knuth, «The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams» (Addison-Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8. [www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz Draft of Fascicle 1b] available for download.
• H. R. Andersen «[www.configit.com/fileadmin/Configit/Documents/bdd-eap.pdf An Introduction to Binary Decision Diagrams]», Lecture Notes, 1999, IT University of Copenhagen.
• Ch. Meinel, T. Theobald, «[www.hpi.uni-potsdam.de/fileadmin/hpi/FG_ITS/books/OBDD-Book.pdf Algorithms and Data Structures in VLSI-Design: OBDD — Foundations and Applications»], Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
• Advanced BDD optimization. — Springer, 2005. — ISBN 978-0-387-25453-1.
• Binary Decision Diagrams: Theory and Implementation. — Springer, 1998. — ISBN 978-1-4419-5047-5.

Ссылки

• [fmv.jku.at/abcd/ ABCD]: The ABCD package by Armin Biere, Johannes Kepler Universität, Linz.
• [www-2.cs.cmu.edu/~modelcheck/bdd.html CMU BDD], BDD package, Carnegie Mellon University, Pittsburgh
• [vlsi.colorado.edu/~fabio/CUDD/ CUDD]: BDD package, University of Colorado, Boulder
• [www.technical-recipes.com/category/binary-decision-diagrams/ Installing CUDD in Windows/Visual Studio environments.]
• [lms.uni-mb.si/biddy/ Biddy]: multi-platform academic BDD package, University of Maribor, Slovenia
• [javabdd.sourceforge.net JavaBDD], a Java port of BuDDy that also interfaces to CUDD, CAL, and JDD
• The Berkeley [embedded.eecs.berkeley.edu/Research/cal_bdd/ CAL] package which does breadth-first manipulation
• A. Costa [www.dei.isep.ipp.pt/~acc/bfunc/ BFunc], includes a BDD boolean logic simplifier supporting up to 32 inputs / 32 outputs (independently)
• [ddd.lip6.fr DDD]: A C++ library with support for integer valued and hierarchical decision diagrams.
• [www.jossowski.de/projects/jinc/jinc.html JINC]: A C++ library developed at University of Bonn, Germany, supporting several BDD variants and multi-threading.

Отрывок, характеризующий Бинарная диаграмма решений

– Наташа, – сказала она, – ты просила меня не говорить с тобой, я и не говорила, теперь ты сама начала. Наташа, я не верю ему. Зачем эта тайна?
– Опять, опять! – перебила Наташа.
– Наташа, я боюсь за тебя.
– Чего бояться?
– Я боюсь, что ты погубишь себя, – решительно сказала Соня, сама испугавшись того что она сказала.
Лицо Наташи опять выразило злобу.
– И погублю, погублю, как можно скорее погублю себя. Не ваше дело. Не вам, а мне дурно будет. Оставь, оставь меня. Я ненавижу тебя.
– Наташа! – испуганно взывала Соня.
– Ненавижу, ненавижу! И ты мой враг навсегда!
Наташа выбежала из комнаты.
Наташа не говорила больше с Соней и избегала ее. С тем же выражением взволнованного удивления и преступности она ходила по комнатам, принимаясь то за то, то за другое занятие и тотчас же бросая их.
Как это ни тяжело было для Сони, но она, не спуская глаз, следила за своей подругой.
Накануне того дня, в который должен был вернуться граф, Соня заметила, что Наташа сидела всё утро у окна гостиной, как будто ожидая чего то и что она сделала какой то знак проехавшему военному, которого Соня приняла за Анатоля.
Соня стала еще внимательнее наблюдать свою подругу и заметила, что Наташа была всё время обеда и вечер в странном и неестественном состоянии (отвечала невпопад на делаемые ей вопросы, начинала и не доканчивала фразы, всему смеялась).
После чая Соня увидала робеющую горничную девушку, выжидавшую ее у двери Наташи. Она пропустила ее и, подслушав у двери, узнала, что опять было передано письмо. И вдруг Соне стало ясно, что у Наташи был какой нибудь страшный план на нынешний вечер. Соня постучалась к ней. Наташа не пустила ее.
«Она убежит с ним! думала Соня. Она на всё способна. Нынче в лице ее было что то особенно жалкое и решительное. Она заплакала, прощаясь с дяденькой, вспоминала Соня. Да это верно, она бежит с ним, – но что мне делать?» думала Соня, припоминая теперь те признаки, которые ясно доказывали, почему у Наташи было какое то страшное намерение. «Графа нет. Что мне делать, написать к Курагину, требуя от него объяснения? Но кто велит ему ответить? Писать Пьеру, как просил князь Андрей в случае несчастия?… Но может быть, в самом деле она уже отказала Болконскому (она вчера отослала письмо княжне Марье). Дяденьки нет!» Сказать Марье Дмитриевне, которая так верила в Наташу, Соне казалось ужасно. «Но так или иначе, думала Соня, стоя в темном коридоре: теперь или никогда пришло время доказать, что я помню благодеяния их семейства и люблю Nicolas. Нет, я хоть три ночи не буду спать, а не выйду из этого коридора и силой не пущу ее, и не дам позору обрушиться на их семейство», думала она.


Анатоль последнее время переселился к Долохову. План похищения Ростовой уже несколько дней был обдуман и приготовлен Долоховым, и в тот день, когда Соня, подслушав у двери Наташу, решилась оберегать ее, план этот должен был быть приведен в исполнение. Наташа в десять часов вечера обещала выйти к Курагину на заднее крыльцо. Курагин должен был посадить ее в приготовленную тройку и везти за 60 верст от Москвы в село Каменку, где был приготовлен расстриженный поп, который должен был обвенчать их. В Каменке и была готова подстава, которая должна была вывезти их на Варшавскую дорогу и там на почтовых они должны были скакать за границу.
У Анатоля были и паспорт, и подорожная, и десять тысяч денег, взятые у сестры, и десять тысяч, занятые через посредство Долохова.
Два свидетеля – Хвостиков, бывший приказный, которого употреблял для игры Долохов и Макарин, отставной гусар, добродушный и слабый человек, питавший беспредельную любовь к Курагину – сидели в первой комнате за чаем.
В большом кабинете Долохова, убранном от стен до потолка персидскими коврами, медвежьими шкурами и оружием, сидел Долохов в дорожном бешмете и сапогах перед раскрытым бюро, на котором лежали счеты и пачки денег. Анатоль в расстегнутом мундире ходил из той комнаты, где сидели свидетели, через кабинет в заднюю комнату, где его лакей француз с другими укладывал последние вещи. Долохов считал деньги и записывал.
– Ну, – сказал он, – Хвостикову надо дать две тысячи.
– Ну и дай, – сказал Анатоль.
– Макарка (они так звали Макарина), этот бескорыстно за тебя в огонь и в воду. Ну вот и кончены счеты, – сказал Долохов, показывая ему записку. – Так?
– Да, разумеется, так, – сказал Анатоль, видимо не слушавший Долохова и с улыбкой, не сходившей у него с лица, смотревший вперед себя.
Долохов захлопнул бюро и обратился к Анатолю с насмешливой улыбкой.
– А знаешь что – брось всё это: еще время есть! – сказал он.
– Дурак! – сказал Анатоль. – Перестань говорить глупости. Ежели бы ты знал… Это чорт знает, что такое!
– Право брось, – сказал Долохов. – Я тебе дело говорю. Разве это шутка, что ты затеял?
– Ну, опять, опять дразнить? Пошел к чорту! А?… – сморщившись сказал Анатоль. – Право не до твоих дурацких шуток. – И он ушел из комнаты.
Долохов презрительно и снисходительно улыбался, когда Анатоль вышел.
– Ты постой, – сказал он вслед Анатолю, – я не шучу, я дело говорю, поди, поди сюда.
Анатоль опять вошел в комнату и, стараясь сосредоточить внимание, смотрел на Долохова, очевидно невольно покоряясь ему.
– Ты меня слушай, я тебе последний раз говорю. Что мне с тобой шутить? Разве я тебе перечил? Кто тебе всё устроил, кто попа нашел, кто паспорт взял, кто денег достал? Всё я.
– Ну и спасибо тебе. Ты думаешь я тебе не благодарен? – Анатоль вздохнул и обнял Долохова.
– Я тебе помогал, но всё же я тебе должен правду сказать: дело опасное и, если разобрать, глупое. Ну, ты ее увезешь, хорошо. Разве это так оставят? Узнается дело, что ты женат. Ведь тебя под уголовный суд подведут…
– Ах! глупости, глупости! – опять сморщившись заговорил Анатоль. – Ведь я тебе толковал. А? – И Анатоль с тем особенным пристрастием (которое бывает у людей тупых) к умозаключению, до которого они дойдут своим умом, повторил то рассуждение, которое он раз сто повторял Долохову. – Ведь я тебе толковал, я решил: ежели этот брак будет недействителен, – cказал он, загибая палец, – значит я не отвечаю; ну а ежели действителен, всё равно: за границей никто этого не будет знать, ну ведь так? И не говори, не говори, не говори!
– Право, брось! Ты только себя свяжешь…
– Убирайся к чорту, – сказал Анатоль и, взявшись за волосы, вышел в другую комнату и тотчас же вернулся и с ногами сел на кресло близко перед Долоховым. – Это чорт знает что такое! А? Ты посмотри, как бьется! – Он взял руку Долохова и приложил к своему сердцу. – Ah! quel pied, mon cher, quel regard! Une deesse!! [О! Какая ножка, мой друг, какой взгляд! Богиня!!] A?
Долохов, холодно улыбаясь и блестя своими красивыми, наглыми глазами, смотрел на него, видимо желая еще повеселиться над ним.
– Ну деньги выйдут, тогда что?
– Тогда что? А? – повторил Анатоль с искренним недоумением перед мыслью о будущем. – Тогда что? Там я не знаю что… Ну что глупости говорить! – Он посмотрел на часы. – Пора!
Анатоль пошел в заднюю комнату.
– Ну скоро ли вы? Копаетесь тут! – крикнул он на слуг.
Долохов убрал деньги и крикнув человека, чтобы велеть подать поесть и выпить на дорогу, вошел в ту комнату, где сидели Хвостиков и Макарин.
Анатоль в кабинете лежал, облокотившись на руку, на диване, задумчиво улыбался и что то нежно про себя шептал своим красивым ртом.
– Иди, съешь что нибудь. Ну выпей! – кричал ему из другой комнаты Долохов.
– Не хочу! – ответил Анатоль, всё продолжая улыбаться.
– Иди, Балага приехал.
Анатоль встал и вошел в столовую. Балага был известный троечный ямщик, уже лет шесть знавший Долохова и Анатоля, и служивший им своими тройками. Не раз он, когда полк Анатоля стоял в Твери, с вечера увозил его из Твери, к рассвету доставлял в Москву и увозил на другой день ночью. Не раз он увозил Долохова от погони, не раз он по городу катал их с цыганами и дамочками, как называл Балага. Не раз он с их работой давил по Москве народ и извозчиков, и всегда его выручали его господа, как он называл их. Не одну лошадь он загнал под ними. Не раз он был бит ими, не раз напаивали они его шампанским и мадерой, которую он любил, и не одну штуку он знал за каждым из них, которая обыкновенному человеку давно бы заслужила Сибирь. В кутежах своих они часто зазывали Балагу, заставляли его пить и плясать у цыган, и не одна тысяча их денег перешла через его руки. Служа им, он двадцать раз в году рисковал и своей жизнью и своей шкурой, и на их работе переморил больше лошадей, чем они ему переплатили денег. Но он любил их, любил эту безумную езду, по восемнадцати верст в час, любил перекувырнуть извозчика и раздавить пешехода по Москве, и во весь скок пролететь по московским улицам. Он любил слышать за собой этот дикий крик пьяных голосов: «пошел! пошел!» тогда как уж и так нельзя было ехать шибче; любил вытянуть больно по шее мужика, который и так ни жив, ни мертв сторонился от него. «Настоящие господа!» думал он.
Анатоль и Долохов тоже любили Балагу за его мастерство езды и за то, что он любил то же, что и они. С другими Балага рядился, брал по двадцати пяти рублей за двухчасовое катанье и с другими только изредка ездил сам, а больше посылал своих молодцов. Но с своими господами, как он называл их, он всегда ехал сам и никогда ничего не требовал за свою работу. Только узнав через камердинеров время, когда были деньги, он раз в несколько месяцев приходил поутру, трезвый и, низко кланяясь, просил выручить его. Его всегда сажали господа.
– Уж вы меня вызвольте, батюшка Федор Иваныч или ваше сиятельство, – говорил он. – Обезлошадничал вовсе, на ярманку ехать уж ссудите, что можете.
И Анатоль и Долохов, когда бывали в деньгах, давали ему по тысяче и по две рублей.
Балага был русый, с красным лицом и в особенности красной, толстой шеей, приземистый, курносый мужик, лет двадцати семи, с блестящими маленькими глазами и маленькой бородкой. Он был одет в тонком синем кафтане на шелковой подкладке, надетом на полушубке.
Он перекрестился на передний угол и подошел к Долохову, протягивая черную, небольшую руку.
– Федору Ивановичу! – сказал он, кланяясь.
– Здорово, брат. – Ну вот и он.
– Здравствуй, ваше сиятельство, – сказал он входившему Анатолю и тоже протянул руку.
– Я тебе говорю, Балага, – сказал Анатоль, кладя ему руки на плечи, – любишь ты меня или нет? А? Теперь службу сослужи… На каких приехал? А?
– Как посол приказал, на ваших на зверьях, – сказал Балага.
– Ну, слышишь, Балага! Зарежь всю тройку, а чтобы в три часа приехать. А?
– Как зарежешь, на чем поедем? – сказал Балага, подмигивая.
– Ну, я тебе морду разобью, ты не шути! – вдруг, выкатив глаза, крикнул Анатоль.
– Что ж шутить, – посмеиваясь сказал ямщик. – Разве я для своих господ пожалею? Что мочи скакать будет лошадям, то и ехать будем.