Бінарна діаграма рішень: відмінності між версіями

[неперевірена версія]

[перевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

Лінійно

Версія за 19:39, 7 березня 2024

Бінарна діаграма рішень (англ. Binary decision diagram) або програма розгалуження — це структура даних в інформатиці, яка використовується для представлення булевої функції. На більш абстрактному рівні, БДР можна розглядати як стиснене представлення множин або відношень. На відміну від інших стиснених представлень, операції виконуються безпосередньо на стислому представлені, тобто без декомпресії. Інші структури даних, які використовуються для представлення булевої функції мають в собі заперечення нормальної форми, пропозіціональний орієнтований ациклічний граф^[en].

Визначення

Булева функція може бути представлена у вигляді орієнтованого ациклічного графа, який складається з декількох вузлів рішень і термінальних вузлів. Існують два типи кінцевих вузлів: 0-термінал і 1-термінал. Кожен вузол рішень $N$ позначений булевою (логічною) змінною $V_{N}$ і має два дочірніх вузли з назвою нижній дочірній та верхній дочірній. Ребро з вузла $V_{N}$ до нижнього (або верхнього) дочірнього вузла являє собою відповідність $V_{N}$ нулю (або 1). Така БДР називається «впорядкованою», якщо різні змінні з'являються в тому ж порядку на всіх шляхах від кореня. БДР називають скороченою, якщо наступні два правила вже були застосовані до його графи:

Злиті будь-які ізоморфні підграфи.
Вилучено будь-який вузол, у якого обидва нащадки ізоморфні.

У більшості випадків під бінарною діаграмою рішень розуміють саме скорочену впорядковану бінарну діаграму рішень (СВБДР). Перевага скороченої впорядкованої БДР в тому, що вона є канонічною (єдиною) для конкретної функції й заданого порядку змінних^[1]. Ця властивість робить СВБДР корисною для перевірки функціональної еквівалентності.

Шлях від кореня до 1-терміналу представляє (можливо частково) набори змінних, для яких задана булева функція приймає значення «істина». Як шлях прямує від кореня до нижнього або верхнього нащадка, так і змінна у вузлі ставиться у відповідність 0 або 1.

Приклад

На малюнку ліворуч зображене бінарне дерево прийняття рішень (без застосування правил скорочення), відповідне наведеної на цьому ж малюнку таблиці істинності для булевої функції $f(x_{1},x_{2},x_{3})$ . Для заданих вхідних значень $x_{1}$ , $x_{2}$ , $x_{3}$ можна визначити значення логічної функції, рухаючись по дереву від кореневого вузла дерева до термінальних вузлів, вибираючи напрямок переходу з вузла $x_{i}$ залежно від вхідного значення $x_{i}$ . Пунктирними лініями на малюнку зображені переходи до молодшого нащадку, а безперервними лініями зображені переходи до старшого нащадку. Наприклад, якщо задано вхідні значення ( $x_{1}=0$ , $x_{2}=1$ , $x_{3}=1$ ), то з кореневого вузла $x_{1}$ необхідно перейти по пунктирній лінії ліворуч (оскільки значення $x_{1}$ дорівнює 0), після цього необхідно перейти по безперервним лініям праворуч (бо значення $x_{2}$ та $x_{3}$ дорівнюють 1). У результаті ми опинимося в 1-термінальному вузлі, тобто значення $f(x_{1}=0,x_{2}=1,x_{3}=1)$ дорівнює 1.

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

Бінарне дерево рішень та таблиця істинності функції $f(x_{1},x_{2},x_{3})={\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}+x_{1}x_{2}+x_{2}x_{3}$

Історія

Основною ідеєю для створення такої структури даних послужило розкладання Шеннона. Будь-яку булеву функцію по одній з вхідних змінних можна розділити на дві підфункції, званих позитивним і негативним доповненням, з яких за принципом if-then-else вибирається тільки одна підфункція залежно від значення вхідної змінної (за якою виконувалося розкладання Шеннона). Представляючи кожну таку підфункцію у вигляді піддерева і продовжуючи розкладання по решті вхідних змінних, можна отримати дерево прийняття рішень, скорочення якого дасть бінарну діаграму рішень. Інформація про використання бінарних діаграм рішень або бінарних розгалужених програм була вперше опублікована в 1959 році в технічному журналі «Bell Systems Technical Journal»^[2]^[3]^[4].

Потенціал для створення ефективних алгоритмів, заснованих на використанні цієї структури даних, досліджував Рендел Брайнт з університету Карнегі — Меллон: його підхід полягав у використанні фіксованого порядку змінних (для однозначності канонічного представлення кожної булевої функції) і повторного використання загальних підграфів (для компактності). Застосування цих двох ключових концепцій дозволяє підвищити ефективність структур даних і алгоритмів для представлення множин і відносин між ними.^[5]^[6] Використання декількома БДР загальних підграфів призвело до появи такої структури даних, як розділювана скорочена впорядкована бінарна діаграма рішень (англ. Shared Reduced Ordered Binary Decision Diagram).^[7] Назва БДР тепер в основному використовується для цієї конкретної структури даних.

Дональд Кнут у своїй відеолекції Fun With Binary Decision Diagrams (BDDs) назвав бінарні діаграми рішень «однією з дійсно фундаментальних структур даних, які з'явилися за останні двадцять п'ять років» і зазначив, що публікація Рендела Брайнта 1986 року, яка пояснила використання бінарних діаграм рішень для маніпуляції над булевими функціями, була деякий час найбільш цитованою публікацією в комп'ютерній науці.

Застосування

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

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

Порядок змінних

Розмір БДР визначається як булевою функцією, так і вибором порядку вхідних змінних. При складанні графа для булевої функції $f(x_{1},\ldots ,x_{n})$ кількість вузлів у найкращому випадку може лінійно залежати від $n$ , а в найгіршому випадку залежність може бути експоненційною при невдалому виборі порядку вхідних змінних. Наприклад, дана булева функція $f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.$ . Якщо використовувати порядок змінних $x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}$ , то знадобиться 2 ^{n + 1} вузлів для представлення функції у вигляді БДР. Ілюструє БДР для функції від 8 змінних зображена на малюнку зліва. А якщо використовувати порядок $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}$ , то можна отримати еквівалентну БДР з 2n + 2 вузлів. Ілюстрована БДР для функції від 8 змінних зображена на малюнку праворуч.

Вибір порядку змінних є критично важливим при використанні таких структур даних на практиці. Проблема знаходження найкращого порядку змінних є NP-складним завданням.^[8] На додаток, NP-складним є навіть завдання знаходження субоптимального порядку змінних, при якому для будь-якої константи c > 1 розмір БДР не більше ніж в c раз більше оптимального.^[9] Однак існують ефективні евристичні методи для розв'язання цієї проблеми.

Крім того, існують такі функції, для яких розмір графа завжди зростає експоненціально з ростом числа змінних, незалежно від порядку змінних. Це належить до функцій множення, що вказує на явну складність факторизації.

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

Логічні операції над БДР

Багато логічних операцій можуть бути виконані безпосередньо над БДР за допомогою алгоритмів, що виконують маніпуляції над графами за поліноміальний час.

кон'юнкція
диз'юнкція
заперечення
екзистенціальна абстракція
універсальна абстракція

Однак повторення цих операцій безліч разів, наприклад, при формуванні кон'юнкцій або диз'юнкцій набору БДР, можуть призвести до експоненціально великого БДР в гіршому випадку. Це відбувається через те, що результатом будь-яких попередніх операцій над двома БДР в загальному випадку може бути БДР з розміром, пропорційним добутку попередніх розмірів, тому для декількох БДР розмір може збільшуватися експоненціально.

Див. також

Примітки

↑ Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986
↑ C. Y. Lee.
↑ Sheldon B. Akers.
↑ Raymond T. Boute, «The Binary Decision Machine as a programmable controller».
↑ Randal E. Bryant.
↑ R. E. Bryant, «Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams» [Архівовано 23 вересня 2015 у Wayback Machine.], ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293—318.
↑ Karl S. Brace, Richard L. Rudell and Randal E. Bryant.
↑ Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, 45(9):993-1002, September 1996.
↑ Detlef Sieling. «The nonapproximability of OBDD minimization.» Information and Computation 172, 103–138. 2002.

Посилання

ABCD [Архівовано 24 жовтня 2020 у Wayback Machine.]: The ABCD package by Armin Biere, Johannes Kepler Universität, Linz.
CMU BDD [Архівовано 26 вересня 2011 у Wayback Machine.], BDD package, Carnegie Mellon University, Pittsburgh
CUDD: BDD package, University of Colorado, Boulder
Installing CUDD in Windows/Visual Studio environments.
Biddy [Архівовано 6 жовтня 2015 у Wayback Machine.]: multi-platform academic BDD package, University of Maribor, Slovenia
JavaBDD [Архівовано 22 квітня 2020 у Wayback Machine.], a Java port of BuDDy that also interfaces to CUDD, CAL, and JDD
The Berkeley CAL package which does breadth-first manipulation
A. Costa BFunc [Архівовано 12 липня 2012 у Wayback Machine.], includes a BDD boolean logic simplifier supporting up to 32 inputs / 32 outputs (independently)
DDD [Архівовано 9 липня 2017 у Wayback Machine.]: A C++ library with support for integer valued and hierarchical decision diagrams.
JINC: A C++ library developed at University of Bonn, Germany, supporting several BDD variants and multi-threading.

[Bryant1986-1] Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986

[Lee-2] C. Y. Lee.

[Akers-3] Sheldon B. Akers.

[4] Raymond T. Boute, «The Binary Decision Machine as a programmable controller».

[Bryant-1986-5] Randal E. Bryant.

[Bryant-1992-6] R. E. Bryant, «Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams» [Архівовано 23 вересня 2015 у Wayback Machine.], ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293—318.

[Brace-7] Karl S. Brace, Richard L. Rudell and Randal E. Bryant.

[Bollig-8] Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, 45(9):993-1002, September 1996.

[Sieling-9] Detlef Sieling. «The nonapproximability of OBDD minimization.» Information and Computation 172, 103–138. 2002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Рядок 1: / Рядок 1: @@
-'''Бінарна діаграма рішень''' ({{lang-en|Binary decision diagram}}) або '''програма розгалуження'''&nbsp;— це [[структура даних]] в [[Інформатика|інформатиці]], яка використовується для представлення [[Булева функція|булевої функції]]. На більш абстрактному рівні, БДР можна розглядати як [[Стиснення даних|стиснене]] представлення [[Множина|множин]] або [[Бінарне відношення|відношень]]. На відміну від інших стиснених представлень, операції виконуються безпосередньо на стислому представлені, тобто без декомпресії. Інші [[структури даних]], які використовуються для представлення [[Булева функція|булевої функції]] включають в себе [[заперечення нормальної форми]],&nbsp; {{Нп|пропозіціональний орієнтований ациклічний граф|||Propositional directed acyclic graph}}.
+'''Бінарна діаграма рішень''' ({{lang-en|Binary decision diagram}}) або '''програма розгалуження'''&nbsp;— це [[структура даних]] в [[Інформатика|інформатиці]], яка використовується для представлення [[Булева функція|булевої функції]]. На більш абстрактному рівні, БДР можна розглядати як [[Стиснення даних|стиснене]] представлення [[Множина|множин]] або [[Бінарне відношення|відношень]]. На відміну від інших стиснених представлень, операції виконуються безпосередньо на стислому представлені, тобто без декомпресії. Інші [[структури даних]], які використовуються для представлення [[Булева функція|булевої функції]] мають в собі [[заперечення нормальної форми]],&nbsp; {{Нп|пропозіціональний орієнтований ациклічний граф|||Propositional directed acyclic graph}}.
 == Визначення ==
-Булева функція може бути представлена у вигляді [[Орієнтований ациклічний граф|орієнтованого ациклічного графа]], який складається з декількох вузлів рішень і термінальних вузлів.&nbsp;Існують два типи кінцевих вузлів: 0-термінал і 1-термінал. Кожен вузол рішень <math>N</math> позначений булевою (логічною) змінною <math>V_N</math> і має два [[Дерево (структура даних)|дочірніх вузли]] з назвою нижній дочірній та верхній дочірній. Ребро з вузла <math>V_N</math> до нижнього (або верхнього) дочірнього вузла являє собою відповідність <math>V_N</math> нулю (або 1). Така БДР називається «впорядкованою», якщо різні змінні з'являються в тому ж порядку на всіх шляхах від кореня. БДР називають скороченою, якщо наступні два правила вже були застосовані до його графу:
+Булева функція може бути представлена у вигляді [[Орієнтований ациклічний граф|орієнтованого ациклічного графа]], який складається з декількох вузлів рішень і термінальних вузлів.&nbsp;Існують два типи кінцевих вузлів: 0-термінал і 1-термінал. Кожен вузол рішень <math>N</math> позначений булевою (логічною) змінною <math>V_N</math> і має два [[Дерево (структура даних)|дочірніх вузли]] з назвою нижній дочірній та верхній дочірній. Ребро з вузла <math>V_N</math> до нижнього (або верхнього) дочірнього вузла являє собою відповідність <math>V_N</math> нулю (або 1). Така БДР називається «впорядкованою», якщо різні змінні з'являються в тому ж порядку на всіх шляхах від кореня. БДР називають скороченою, якщо наступні два правила вже були застосовані до його графи:
 * Злиті будь-які [[Ізоморфізм графів|ізоморфні]] підграфи.
 * Вилучено будь-який вузол, у якого обидва нащадки ізоморфні.
-У більшості випадків під '''бінарною діаграмою рішень''' розуміють саме '''скорочену впорядковану бінарну діаграму рішень''' ('''СВБДР'''). Перевага скороченої впорядкованої БДР в тому, що вона є канонічною (єдиною) для конкретної функції і заданого порядку змінних<ref name="Bryant1986">Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986</ref>.&nbsp; Ця властивість робить СУБДР корисною для перевірки функціональної еквівалентності.
+У більшості випадків під '''бінарною діаграмою рішень''' розуміють саме '''скорочену впорядковану бінарну діаграму рішень''' ('''СВБДР'''). Перевага скороченої впорядкованої БДР в тому, що вона є канонічною (єдиною) для конкретної функції й заданого порядку змінних<ref name="Bryant1986">Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986</ref>.&nbsp; Ця властивість робить СВБДР корисною для перевірки функціональної еквівалентності.
 Шлях від кореня до 1-терміналу представляє (можливо частково) набори змінних, для яких задана булева функція приймає значення «істина». Як шлях прямує від кореня до нижнього або верхнього нащадка, так і змінна у вузлі ставиться у відповідність 0 або 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.
+На малюнку ліворуч зображене бінарне [[дерево прийняття рішень]] (без застосування правил скорочення), відповідне наведеної на цьому ж малюнку [[таблиці істинності]] для булевої функції <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.
 Бінарне дерево прийняття рішень на малюнку ліворуч можна перетворити в бінарну діаграму рішень шляхом застосування двох правил скорочення. БДР, яка буде отримана після скорочення, зображена на малюнку праворуч.
@@ Рядок 24: / Рядок 24: @@
 Потенціал для створення ефективних алгоритмів, заснованих на використанні цієї структури даних, досліджував [[Рендел Брайнт]] з [[Університет Карнегі-Меллон|університету Карнегі&nbsp;— Меллон]]: його підхід полягав у використанні фіксованого порядку змінних (для однозначності канонічного представлення кожної булевої функції) і повторного використання загальних підграфів (для компактності). Застосування цих двох ключових концепцій дозволяє підвищити ефективність структур даних і алгоритмів для представлення множин і відносин між ними.<ref name="Bryant-1986">Randal E. Bryant. </ref><ref name="Bryant-1992">R. E. Bryant, «[http://www.cs.cmu.edu/~bryant/pubdir/acmcs92.ps Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams»] {{Webarchive|url=https://web.archive.org/web/20150923224517/http://www.cs.cmu.edu/~bryant/pubdir/acmcs92.ps |date=23 вересня 2015 }}, ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293—318.</ref> Використання декількома БДР загальних підграфів призвело до появи такої структури даних, як розділювана скорочена впорядкована бінарна діаграма рішень ({{lang-en|Shared Reduced Ordered Binary Decision Diagram}}).<ref name="Brace">Karl S. Brace, Richard L. Rudell and Randal E. Bryant. </ref> Назва БДР тепер в основному використовується для цієї конкретної структури даних.
-[[Дональд Кнут]] в своїй відеолекції [https://web.archive.org/web/20111101143950/http://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)] назвав бінарні діаграми рішень «однією з дійсно фундаментальних структур даних, які з'явилися за останні двадцять п'ять років» і зазначив, що публікація [[Рендел Брайнт|Рендела Брайнта]] 1986 року, яка пояснила використання бінарних діаграм рішень для маніпуляції над булевими функціями, була деякий час найбільш цитованою публікацією в комп'ютерній науці.
+[[Дональд Кнут]] у своїй відеолекції [https://web.archive.org/web/20111101143950/http://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)] назвав бінарні діаграми рішень «однією з дійсно фундаментальних структур даних, які з'явилися за останні двадцять п'ять років» і зазначив, що публікація [[Рендел Брайнт|Рендела Брайнта]] 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 <sup> '' n '' + 1 </sup> вузлів для представлення функції у вигляді БДР. Ілюструє БДР для функції від 8 змінних зображена на малюнку зліва. А якщо використовувати порядок <math> x_1 <x_2 <x_3 <x_4 <\cdots <x_{2n-1} <x_{2n} </math>, то можна отримати еквівалентну БДР з 2''n '' + 2 вузлів. Ілюстрована БДР для функції від 8 змінних зображена на малюнку праворуч.
+Розмір БДР визначається як булевою функцією, так і вибором порядку вхідних змінних. При складанні графа для булевої функції <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 <sup> '' n '' + 1 </sup> вузлів для представлення функції у вигляді БДР. Ілюструє БДР для функції від 8 змінних зображена на малюнку зліва. А якщо використовувати порядок <math> x_1 <x_2 <x_3 <x_4 <\cdots <x_{2n-1} <x_{2n} </math>, то можна отримати еквівалентну БДР з 2''n '' + 2 вузлів. Ілюстрована БДР для функції від 8 змінних зображена на малюнку праворуч.
 {| align="center"
@@ Рядок 40: / Рядок 40: @@
 |}
 Вибір порядку змінних є критично важливим при використанні таких структур даних на практиці. Проблема знаходження найкращого порядку змінних є NP-складним завданням.<ref name="Bollig">Beate Bollig, Ingo Wegener. [http://dx.doi.org/10.1109/12.537122 Improving the Variable Ordering of OBDDs Is NP-Complete], IEEE Transactions on Computers, 45(9):993-1002, September 1996.
-</ref> Більш того, [[NP-складна задача|NP-складним]] є навіть завдання знаходження субоптимального порядку змінних, при якому для будь константи c > 1 розмір БДР не більше ніж в c раз більше оптимального.<ref name="Sieling">Detlef Sieling. «The nonapproximability of OBDD minimization.» Information and Computation 172, 103–138. 2002.</ref> Однак існують ефективні евристичні методи для вирішення цієї проблеми.
+</ref> На додаток, [[NP-складна задача|NP-складним]] є навіть завдання знаходження субоптимального порядку змінних, при якому для будь-якої константи c > 1 розмір БДР не більше ніж в c раз більше оптимального.<ref name="Sieling">Detlef Sieling. «The nonapproximability of OBDD minimization.» Information and Computation 172, 103–138. 2002.</ref> Однак існують ефективні евристичні методи для розв'язання цієї проблеми.
-Крім того, існують такі функції, для яких розмір графа завжди зростає експоненціально з ростом числа змінних, незалежно від порядку змінних. Це відноситься до функцій множення, що вказує на явну складність [[Факторизація|факторизації]].
+Крім того, існують такі функції, для яких розмір графа завжди зростає експоненціально з ростом числа змінних, незалежно від порядку змінних. Це належить до функцій множення, що вказує на явну складність [[Факторизація|факторизації]].
 Дослідження бінарних діаграм рішень привели до появи безлічі суміжних видів графів, таких, як BMD ([[Binary Moment Diagrams]]), ZDD ([[Zero Suppressed Decision Diagram]]), FDD ([[Free Binary Decision Diagrams]]), PDD ([[Parity decision Diagrams]]), і MTBDDs ([[Multiple terminal BDDs]]).

Бінарна діаграма рішень: відмінності між версіями

Версія за 19:39, 7 березня 2024

Зміст

Визначення

Приклад

Історія

Застосування

Порядок змінних

Логічні операції над БДР

Див. також

Примітки

Рекомендована література

Посилання

Навігаційне меню

Бінарна діаграма рішень: відмінності між версіями

Версія за 19:39, 7 березня 2024

Визначення

Приклад

Історія

Застосування

Порядок змінних

Логічні операції над БДР

Див. також

Примітки

Рекомендована література

Посилання

Навігаційне меню

Пошук