Diagrama de decizie binară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 ianuarie 2020; verificările necesită 3 modificări .

O diagramă de decizie binară ( BDE ) sau un program de ramificare este o formă de reprezentare a unei funcții booleene a variabilelor ca un graf aciclic direcționat , constând din noduri de decizie interne (etichetate ), fiecare dintre ele având doi copii și două noduri terminale (etichetate 0 ). și 1), fiecare dintre acestea corespunde uneia dintre cele două valori ale funcției booleene. În literatura străină, diagramele de decizie binare și programele de ramificare sunt numite diagramă de decizie binară ( BDD ) și , respectiv , programe de ramificare ( BP ). $f(x_{1},x_{2},...,x_{n})$ $n$ $x_{i}$

Definiție

O funcție booleană poate fi reprezentată ca un graf aciclic direcționat , constând din mai multe noduri de decizie interne și două noduri terminale, numite nod 0-terminal și un nod 1-terminal. Fiecare nod de decizie intern dintr-un nivel este etichetat cu o variabilă booleană și are doi copii , numiți copil junior și copil senior. Trecerea de la un nod intern la un copil mai mic sau mai mare se realizează în funcție de valoarea variabilei (0 sau respectiv 1). Pentru valorile date , calea de la nodul rădăcină la nodul 1-terminal corespunde faptului că pe aceste valori de intrare funcția booleană ia valoarea 1. $f(x_{1},x_{2},...,x_{n})$ $i$ $x_{i}$ $x_{i}$ $x_{i}$ $x_{1},x_{2},...,x_{n}$ $f(x_{1},x_{2},...,x_{n})$

Se spune că un BDR este ordonat dacă diferite variabile apar în aceeași ordine în toate căile de la nodul rădăcină al graficului la unul dintre vârfurile terminale. În același timp, unele variabile din căi pot fi absente dacă operația de reducere a fost efectuată anterior pe grafic.

Un BDR se numește abreviat dacă graficului i se aplică următoarele două reguli de abreviere:

Fuzionarea oricăror subgrafe izomorfe .
Eliminarea tuturor nodurilor cu copii izomorfi .

În cele mai multe cazuri, o diagramă de decizie binară este înțeleasă ca o diagramă de decizie binară ordonată redusă ( SUBDR ). Avantajul unui BDD ordonat redus este că este canonic (unic) pentru o anumită funcție și o anumită ordine de variabile. [1] Această proprietate face ca RUBMS să fie util pentru testarea echivalenței funcționale.

Exemplu

Figura din stânga arată un arbore de decizie binar (fără aplicarea regulilor de reducere) corespunzător tabelului de adevăr pentru funcția booleană prezentată în aceeași figură . Pentru valorile de intrare date , , puteți determina valoarea funcției booleene deplasându-vă de-a lungul arborelui de la nodul rădăcină al arborelui la nodurile terminale, alegând direcția de tranziție de la nod în funcție de valoarea de intrare . Liniile punctate din figură reprezintă tranziții către un copil mai mic, iar liniile continue reprezintă tranziții către un copil mai mare. De exemplu, dacă sunt date valorile de intrare ( , , ), atunci de la nodul rădăcină trebuie să mergeți de-a lungul liniei punctate la stânga (deoarece valoarea este 0), după aceea trebuie să mergeți de-a lungul liniilor continue la dreapta (deoarece valorile și sunt egale cu 1). Ca rezultat, vom ajunge într-un nod cu 1 terminal, adică valoarea este 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}$ $x_{2}$ $x_{3}$ $f(x_{1}=0,x_{2}=1,x_{3}=1)$

Arborele de decizie binar din figura din stânga poate fi convertit într-o diagramă de decizie binară prin aplicarea a două reguli de reducere. BDR -ul rezultat este prezentat în figura din dreapta.

Istorie

Ideea principală pentru crearea unei astfel de structuri de date a fost descompunerea Shannon . Orice funcție booleană de pe una dintre variabilele de intrare poate fi împărțită în două subfuncții, numite complement pozitiv și negativ, din care se selectează o singură subfuncție conform principiului dacă-atunci-altfel , în funcție de valoarea variabilei de intrare (pe care s-a realizat expansiunea Shannon). Reprezentând fiecare astfel de subfuncție ca un subarboresc și continuând expansiunea în variabilele de intrare rămase, se poate obține un arbore de decizie , a cărui reducere va da o diagramă de decizie binară . Informațiile despre utilizarea diagramelor de decizie binare sau a programelor binare de ramificare au fost publicate pentru prima dată în 1959 în Jurnalul tehnic Bell Systems [2] [3] [4] . Un BDD numit forma canonică între paranteze a fost implementat de Mamrukov [5] în CAD pentru analiza circuitelor independente de viteză. Potențialul de a crea algoritmi eficienți bazați pe această structură de date a fost explorat de Randal Bryant de la Universitatea Carnegie Mellon : abordarea sa a fost să folosească o ordine fixă a variabilelor (pentru o reprezentare canonică unică a fiecărei funcții booleene) și reutilizarea subgrafelor comune (pentru compactitate). ). Aplicarea acestor două concepte cheie face posibilă creșterea eficienței structurilor de date și a algoritmilor de reprezentare a mulțimilor și a relațiilor dintre ele. [6] [7] Utilizarea subgrafelor comune de către mai multe BDR-uri a condus la apariția structurii de date Shared Reduced Ordered Binary Decision Diagram . [8] Numele BDR este acum folosit în principal pentru această structură de date particulară.

Donald Knuth , în prelegerea sa video Fun With Binary Decision Diagrams (BDD), a numit diagramele binare de decizie „ una dintre structurile de date cu adevărat fundamentale care au apărut în ultimii douăzeci și cinci de ani ” și a remarcat că publicația lui Randal Bryant din 1986 [6] ] , care a evidențiat utilizarea diagramelor binare de decizie pentru manipularea funcțiilor booleene, a fost de ceva timp publicația cea mai citată în informatică.

Aplicație

BDR-urile sunt utilizate pe scară largă în sistemele de proiectare asistată de computer (CAD) pentru sinteza circuitelor logice și în verificarea formală .

În electronică, fiecare BDR specific (chiar nu redus și neordonat) poate fi implementat direct prin înlocuirea fiecărui nod cu un multiplexor cu două intrări și o ieșire.

Ordinea variabilelor

Mărimea BDR este determinată atât de o funcție booleană, cât și de alegerea ordinii variabilelor de intrare. La compilarea unui grafic pentru o funcție booleană, numărul de noduri în cel mai bun caz poate depinde liniar de , iar în cel mai rău caz, dependența poate fi exponențială cu o alegere nereușită a ordinii variabilelor de intrare. De exemplu, având în vedere o funcție booleană. Dacă utilizați ordinea variabilelor , atunci aveți nevoie de 2 n +1 noduri pentru a reprezenta funcția sub forma unui BDD. Un BDD ilustrativ pentru o funcție de 8 variabile este prezentat în figura din stânga. Și dacă utilizați comanda , atunci puteți obține un BDR echivalent de la 2 n +2 noduri. Un BDD ilustrativ pentru o funcție de 8 variabile este prezentat în figura din dreapta. $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}}$ $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{{2n-1}}<x_{{2n}}$

Alegerea ordinii variabilelor este critică atunci când se utilizează astfel de structuri de date în practică. Problema găsirii celei mai bune ordine a variabilelor este o problemă NP-completă . [9] Mai mult, chiar și problema găsirii unei ordine suboptimale a variabilelor este NP-complet , astfel încât pentru orice constantă c > 1 dimensiunea BDD este de cel mult c ori mai mare decât cea optimă. [10] Cu toate acestea, există euristici eficiente pentru a rezolva această problemă.

În plus, există funcții pentru care dimensiunea graficului crește întotdeauna exponențial pe măsură ce crește numărul de variabile, indiferent de ordinea variabilelor. Acest lucru se aplică funcțiilor de multiplicare, indicând complexitatea absolută a factorizării .

Cercetările privind diagramele binare de decizie au condus la apariția multor tipuri de grafice înrudite, cum ar fi BMD ( Binary Moment Diagrams ), ZDD ( Zero Suppressed Decision Diagram ), FDD ( Free Binary Decision Diagrams ), PDD ( Parity decision Diagrams ) și MTBDD-uri (BDD-uri cu mai multe terminale).

Operații logice pe diagrame binare de decizie

Multe operații logice ( conjuncție , disjuncție , negație ) pot fi efectuate direct pe BDR folosind algoritmi care efectuează manipulări grafice în timp polinomial. Cu toate acestea, repetarea acestor operații de multe ori, de exemplu, atunci când se formează conjuncții sau disjuncții ale unui set de BDD-uri, poate duce la un BDD exponențial mare în cel mai rău caz. Acest lucru se datorează faptului că orice operațiuni anterioare pe două BDR-uri poate duce, în general, la un BDR cu o dimensiune proporțională cu produsul dimensiunilor anterioare, astfel încât pentru mai multe BDR-uri dimensiunea poate crește exponențial.

Vezi și

Note

↑ Algoritmi bazați pe grafice pentru manipularea funcției booleene, Randal E. Bryant, 1986
↑ Cy Lee. „Reprezentarea circuitelor de comutare prin programe de decizie binară”. Bell Systems Technical Journal, 38:985-999, 1959.
↑ Sheldon B. Akers. Binary Decision Diagrams Arhivat 7 august 2007 la Wayback Machine (link descendent din 05/13/2013 [3458 zile] - istoric ) , IEEE Transactions on Computers, C-27(6):509-516, iunie 1978.
↑ Raymond T. Boute, „The Binary Decision Machine as a programable controller”. Buletinul informativ EUROMICRO , vol. 1(2):16-22, ianuarie 1976
↑ Yu. V. Mamrukov, Analiza circuitelor aperiodice și a proceselor asincrone. Teza de doctorat. LETI, 1984, 219p.
↑ 1 2 Randal E. Bryant. „ Algoritmi bazați pe grafice pentru manipularea funcției booleene Arhivat 23 septembrie 2015 la Wayback Machine .” IEEE Transactions on Computers, C-35(8):677-691, 1986.
↑ RE Bryant, „ Simbolic Boolean Manipulation with Ordered Binary Decision Diagrams” Arhivat 23 septembrie 2015 la Wayback Machine , ACM Computing Surveys, Vol. 24, nr. 3 (septembrie, 1992), pp. 293-318.
↑ Karl S. Brace, Richard L. Rudell și Randal E. Bryant. „ Implementarea eficientă a unui pachet BDD” . În Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), paginile 40-45. IEEE Computer Society Press, 1990.
↑ Beate Bollig, Ingo Wegener. Îmbunătățirea ordonării variabile a OBDD-urilor este NP-Complete , IEEE Transactions on Computers, 45(9):993-1002, septembrie 1996.
↑ Detlef Seeling. „Neaproximabilitatea minimizării OBDD”. Informare și calcul 172, 103-138. 2002.

R. Ubar, „Test Generation for Digital Circuits Using Alternative Graphs (in Russian)”, în Proc. Universitatea Tehnică din Tallinn, 1976, Nr.409, Universitatea Tehnică din Tallinn, Tallinn, Estonia, pp. 75–81.

Lectură recomandată

DE Knuth, „Arta programării computerelor Volumul 4, Fasciculă 1: Trucuri și tehnici pe biți; Diagrame de decizie binară” (Addison-Wesley Professional, 27 martie 2009) viii+260pp, ISBN 0-321-58050-8 . Schița de fascicul 1b disponibilă pentru descărcare.
H.R. Andersen „ An Introduction to Binary Decision Diagrams ”, Note de curs, 1999, Universitatea IT din Copenhaga.
Ch. Meinel, T. Theobald, „ Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications” , Springer-Verlag, Berlin, Heidelberg, New York, 1998. Manual complet disponibil pentru descărcare.
Rüdiger Ebendt; Gorschwin Fey; Rolf Drechsler. Optimizare avansată BDD . — Springer, 2005. - ISBN 978-0-387-25453-1 .
Bernd Becker; Rolf Drechsler. Diagrame binare de decizie : teorie și implementare . — Springer, 1998. - ISBN 978-1-4419-5047-5 .

Link -uri

ABCD : Pachetul ABCD de Armin Biere, Johannes Kepler Universität, Linz.
CMU BDD , pachet BDD, Universitatea Carnegie Mellon, Pittsburgh
CUDD : pachet BDD, Universitatea din Colorado, Boulder
Instalarea CUDD în medii Windows/Visual Studio.
Biddy : pachet BDD academic multiplatform, Universitatea din Maribor, Slovenia
JavaBDD , un port Java al lui BuDDy care se interfață și cu CUDD, CAL și JDD
Pachetul Berkeley CAL care face manipularea pe lățimea întâi
A. Costa BFunc , include un simplificator logic boolean BDD care acceptă până la 32 de intrări / 32 de ieșiri (independent)
DDD : O bibliotecă C++ cu suport pentru diagrame de decizie cu valori întregi și ierarhice.
JINC : O bibliotecă C++ dezvoltată la Universitatea din Bonn, Germania, care acceptă mai multe variante BDD și multi-threading.

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă