Бінарна діаграма рішень
Бінарна діаграма рішень (БДР) або програма з розгалуженням є формою представлення булевої функції від змінних у вигляді спрямованого ациклического графа. що складається з внутрішніх вузлів рішень (позначених), кожен з яких має по два нащадка. і двох термінальних вузлів (помічених 0 і 1), кожен з яких відповідає одному з двох значень булевої функції. У зарубіжній літературі бінарні діаграми рішень і програми з розгалуженням називаються binary decision diagram (BDD) і branching programs (BP) відповідно.
визначення
Булеву функцію можна представити у вигляді спрямованого ациклического графа. що складається з декількох внутрішніх вузлів рішень і двох термінальних вузлів, званих 0-термінальний вузол і 1-термінальний вузол. Кожен внутрішній вузол рішень на рівні позначений булевої змінної і має по два нащадка. званих молодшим нащадком і старшим нащадком. Перехід від внутрішнього вузла до молодшого або старшого нащадка виконується в залежності від значення змінної (0 або 1 відповідно). Для заданих значень шлях від кореневого вузла до 1-термінального вузла відповідають тому, що на цих вхідних значеннях булева функція приймає значення 1.
БДР називається впорядкованою. якщо різні змінні з'являються в тому ж порядку на всьому шляху від кореневого вузла графа. БДР називається скороченою. якщо для графа застосовані наступні два правила скорочення:
У більшості випадків під бінарної діаграмою рішень розуміють саме скорочену впорядковану бінарну діаграму рішень (СУБДР). Перевага скороченою впорядкованої БДР в тому, що вона є канонічною (унікальної) для конкретної функції і заданого порядку змінних. [1] Ця властивість робить СУБДР корисною для перевірки функціональноїеквівалентності.
На малюнку зліва зображено бінарне дерево прийняття рішень (без застосування правил скорочення), відповідне наведеної на цьому ж малюнку таблиці істинності для булевої функції. Для заданих вхідних значень,, можна визначити значення булевої функції, рухаючись по дереву від кореневого вузла дерева до термінальних вузлів, вибираючи напрямок переходу з вузла в залежності від вхідного значення. Пунктирними лініями на малюнку зображені переходи до молодшого нащадка, а безперервними лініями зображені переходи до старшого нащадка. Наприклад, якщо задані вхідні значення (,,), то з кореневого вузла необхідно перейти по пунктирною лінії вліво (так як значення дорівнює 0), після цього необхідно перейти по безперервним лініях вправо (так як значення та є рівними 1). В результаті ми опинимося в 1-термінальному вузлі, тобто значення дорівнює 1.
Бінарне дерево прийняття рішень на малюнку зліва можна перетворити в бінарну діаграму рішень шляхом застосування двох правил скорочення. Результуюча БДР зображена на малюнку справа.
Бінарне дерево прийняття рішень, побудоване по таблиці істинності для функції
Скорочена БДР для функції f
Потенціал для створення ефективних алгоритмів, заснованих на використанні цієї структури даних, досліджував Randal Bryant з університету Карнегі - Меллон. його підхід полягав у використанні фіксованого порядку змінних (для однозначності канонічного представлення кожної булевої функції) і повторного використання загальних подграфов (для компактності). Примение цих двох ключових концепцій дозволяє підвищити ефективність структур даних і алгоритмів для подання множин і відносин між ними. [5] [6] Використання декількома БДР загальних подграфов призвело до появи такої структури даних як колективна скорочена впорядкована бінарна діаграма рішень (Shared Reduced Ordered Binary Decision Diagram). [7] Назва БДР тепер в основному використовується для цієї конкретної структури даних.
застосування
В електроніці кожна конкретна БДР (навіть не скорочена і не впорядкована) може бути безпосередньо реалізована заміною кожного вузла на мультиплексор з двома входами і одним виходом.
порядок змінних
Розмір БДР визначається як булевої функцією, так і вибором порядку вхідних змінних. При складанні графа для булевої функції кількість вузлів в кращому випадку може лінійно залежати від, а в гіршому випадку залежність може бути експоненційної при невдалому виборі порядку вхідних змінних. Наприклад, дана булева функція Якщо використовувати порядок змінних, то знадобиться 2 n +1 вузлів для представлення функції у вигляді БДР. Ілюструє БДР для функції від 8 змінних зображена на малюнку зліва. А якщо використовувати порядок, то можна отримати еквівалентну БРД з 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), and 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.
рекомендована література
- ABCD. The ABCD package by Armin Biere, Johannes Kepler Universität, Linz.
- CMU BDD. BDD package, Carnegie Mellon University, Pittsburgh
- CUDD. BDD package, University of Colorado, Boulder
- Installing CUDD in Windows / Visual Studio environments.
- Biddy. multi-platform academic BDD package, University of Maribor, Slovenia
- JavaBDD. 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. includes a BDD boolean logic simplifier supporting up to 32 inputs / 32 outputs (independently)
- DDD. 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.
Дивитися що таке "Бінарна діаграма рішень" в інших словниках:
Стек - Просте уявлення стека Цей термін має також інші значення див. Стек (значення). Стек (англ. Stack стоп ... Вікіпедія
Черга (програмування) - Цей термін має також інші значення див. Черга. Черга структура даних з дисципліною доступу до елементів «перший прийшов перший вийшов» (FIFO, First In First Out). Додавання елемента (прийнято позначати словом ... ... Вікіпедія
Асоціативний масив - (словник) абстрактний тип даних (інтерфейс до сховища даних), що дозволяє зберігати пари виду «(ключ, значення)» і підтримує операції додавання пари, а також пошуку і видалення пари по ключу: INSERT (ключ, значення) FIND ( ключ) ... ... Вікіпедія
Хеш-таблиця - Хеш таблиця це структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і виконувати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення пари по ... ... Вікіпедія
Структура даних - Бінарне дерево, простий приклад ветвящейся зв'язковою структури даних. Структура даних (англ. Data structure) програмна одиниця, що дозволяє храни ... Вікіпедія
Зв'язний список - В інформатиці, зв'язний список базова динамічна структура даних, що складається з вузлів, кожен з яких містить як власне дані, так і одну або дві посилання ( «зв'язки») на наступний і / або попередній вузол списку. [1] Принциповим ... ... Вікіпедія
Двійкове дерево пошуку - Тип Дерево Тимчасова складність в Про символіку В середньому В гіршому випадку Витрата пам'яті O (n) O (n) Пошук O (h) O (n) Вставка O (h) O (n) Видалення O (h) O (n) де h висота дерева ... Вікіпедія
Список з пропусками - (англ. Skip List) імовірнісна структура даних, заснована на кількох паралельних відсортованих зв'язкових списках з ефективністю, яку можна порівняти з двійковим деревом (порядку O (log n) середній час для більшості операцій). В основі ... ... Вікіпедія