Diagramă de decizie binară
O diagramă de decizie binară (BDR) sau un program de ramificare este o formă de reprezentare a unei funcții booleene a variabilelor sub forma unui grafic aciclic direcționat. alcătuite din noduri interne de soluții (etichetate), fiecare dintre ele având câte doi descendenți fiecare. și două noduri terminale (etichetate 0 și 1), fiecare dintre acestea corespund uneia dintre cele două valori ale funcției Boolean. În literatura străină, diagramele de decizie binară și programele de ramificare sunt denumite diagrama deciziei binare (BDD) și, respectiv, programele de ramificare (BP).
definiție
Funcția booleană poate fi reprezentată ca un grafic aciclic direcționat. alcătuită din mai multe noduri de soluție internă și două noduri terminale, numită nod terminal 0 și nod terminal 1. Fiecare nod de decizie intern la nivel este marcat cu o variabilă booleană și are doi copii. numit cel mai tânăr descendent și copilul senior. Trecerea de la nodul interior la copilul cel mai mic sau cel mai înalt se efectuează î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ă la aceste valori de intrare funcția Boolean ia valoarea 1.
BDR se numește ordonat. dacă variabilele diferite apar în aceeași ordine în întregime de la nodul rădăcină al graficului. BDR se numește abreviat. Dacă în grafic sunt aplicate următoarele două reguli de reducere:
În majoritatea cazurilor, o diagramă de decizie binară este înțeleasă ca diagrama binară de decizie ordonată abreviat (DBDE). Avantajul unui BDD ordonat scurt este acela că este canonic (unic) pentru o anumită funcție și o ordine dată de variabile. [1] Această proprietate face ca DBDE să fie utilă pentru verificarea echivalenței funcționale.
Cifra din stânga arată un arbore binar de decizie (fără aplicarea regulilor de reducere) care corespunde tabelului de adevăr pentru funcția Boolean prezentată în aceeași figură. Pentru valorile de intrare date, se poate determina valoarea unei funcții booleene, se deplasează arborele de la nodul rădăcină la nodurile terminale ale arborelui, alegând direcția de tranziție de la nodul în funcție de valorile de intrare. Dungile liniare din figură prezintă tranziții către cel mai tânăr descendent, iar liniile continue arată tranziții către descendentul superior. De exemplu, în cazul în care valorile de intrare set (,,), din nodul rădăcină trebuie să meargă de-a lungul liniei punctate spre stânga (deoarece valoarea este 0), atunci trebuie să mergi la linii continue la dreapta (deoarece valorile sunt egale și 1). Ca urmare, ne aflăm într-un nod 1-terminal, care este, valoarea este 1.
Arborele binar de decizie din figura stângă poate fi transformat într-o diagramă de decizie binară prin aplicarea a două reguli de reducere. BDR rezultată este prezentată în figura din dreapta.
Un arbore binar de decizie construit dintr-o tabelă de adevăr pentru o funcție
BDF redus pentru funcția f
Potențialul de a crea algoritmi eficienți bazați pe utilizarea acestei structuri de date a fost explorat de Randal Bryant de la Universitatea Carnegie-Mellon. Abordarea lui a fost de a utiliza un ordin fix de variabile (pentru reprezentarea canonică unicitatea fiecare funcție booleană) și reutilizarea subgrafurilor comune (pentru compactitatea). Aplicarea acestor două concepte cheie permite îmbunătățirea eficienței structurilor de date și algoritmilor pentru reprezentarea seturilor și a relațiilor dintre ele. [5] [6] Utilizarea mai multor subgrafurilor comune BDR a condus la apariția unei astfel de structuri de date ca o diagramă decizie partajată condensată ordonate binar (Shared redusă comandat de decizie Diagrama binar). [7] Numele BDR este acum utilizat în principal pentru această structură specifică de date.
cerere
În electronică, fiecare BDR particular (care nu este chiar scurtat și neordonat) poate fi implementat direct prin înlocuirea fiecărui nod cu un multiplexor cu două intrări și o ieșire.
Ordinea variabilelor
Dimensiunea BDR este determinată atât de funcția booleană, cât și de alegerea ordinii variabilelor de intrare. Atunci când se compilează un grafic pentru o funcție booleană, numărul de noduri în cel mai bun caz poate depinde liniar și, în cel mai rău caz, dependența poate fi exponențială pentru o alegere nereușită a ordinii variabilelor de intrare. De exemplu, având în vedere funcția booleană. Dacă folosim ordinea variabilelor, atunci avem nevoie de 2 node pentru a reprezenta funcția BDR. BDR ilustrativ pentru o funcție de 8 variabile este prezentată în figura din stânga. Și dacă utilizați comanda, puteți obține un BRD echivalent de noduri 2n +2. BDR ilustrativ pentru o funcție de 8 variabile este prezentată în figura din dreapta.
O BDD similară pentru o alegere reușită a ordinii variabilelor
Alegerea ordinii variabilelor este critică atunci când se utilizează astfel de structuri de date în practică. Problema găsirii celei mai bune ordini a variabilelor este o problemă NP-completă. [8] Mai mult decât atât, NP-completă este chiar problema găsirii unei ordini suboptimale a variabilelor astfel încât pentru orice constanță c> 1 dimensiunea BDR este de cel mult c ori mai mare decât cea optimă. [9] Cu toate acestea, există metode eficiente euristice pentru rezolvarea acestei probleme.
În plus, există funcții pentru care dimensiunea graficului crește întotdeauna exponențial cu un număr tot mai mare de variabile, indiferent de ordinea variabilelor. Aceasta se referă la funcțiile de multiplicare, ceea ce indică o complexitate evidentă a factorizării.
Cercetare diagrame de decizie binare au condus la apariția multor tipuri legate de grafice, cum ar fi DMO (Moment binar diagrame), ZDD (Zero Suprimată Decizia diagrama), FDD (gratuit binar de decizie diagrame), PDD (decizie Paritatea diagrame), și MTBDDs (BDDS terminale multiple ).
Operații logice pe diagrame de decizie binară
Multe dintre operațiile logice (conjuncție. Disjuncție. Negație) pot fi formate direct peste BDR prin algoritmi care efectuează manipularea graficelor în timp polinomial. Cu toate acestea, repetarea acestor operații, o pluralitate de ori, de exemplu, în timpul formării conjuncțiilor sau disjuncțiilor set BDR poate duce la o BDR exponențial mare în cel mai rău. Acest lucru se datorează faptului că rezultatul oricăror operațiuni anterioare pe două BDR pot fi, în general BDR într-o mărime proporțională cu produsul dintre dimensiunile de mai sus, astfel încât pentru mai multe dimensiune BDR poate crește exponențial.
notițe
- R. Ubar, "Generarea testelor pentru circuite digitale folosind grafice alternative (în engleză)", în Proc. Universitatea Tehnică din Tallinn, 1976, nr.409, Universitatea Tehnică din Tallinn, Tallinn, Estonia, pp. 75-81.
Literatură recomandată
- ABCD. Pachetul ABCD de Armin Biere, Johannes Kepler Universität, Linz.
- CMU BDD. BDD pachet, Universitatea Carnegie Mellon, Pittsburgh
- CUDD. BDD pachet, Universitatea din Colorado, Boulder
- Instalarea CUDD în medii Windows / Visual Studio.
- Biddy. multi-platformă BDD pachet academic, Universitatea din Maribor, Slovenia
- JavaBDD. un port Java de BuDDy care interfețează de asemenea cu CUDD, CAL și JDD
- Pachetul CAL din Berkeley, care are o manipulare la scară largă
- A. Costa BFunc. include un simplificator logic boolean BDD care suportă până la 32 intrări / 32 ieșiri (independent)
- DDD. O bibliotecă C ++ cu suport pentru diagrame de decizie cu valoare întreagă și ierarhică.
- JINC. O bibliotecă C ++ dezvoltată la Universitatea din Bonn, Germania, care susține mai multe variante BDD și multi-threading.
Vedeți ce este "diagrama deciziei binare" în alte dicționare:
Stack - Reprezentare simplă în stivă Acest termen are alte semnificații, vezi Stack (values). Stack (stiva engleză ... Wikipedia
Coada (programare) - Acest termen are alte sensuri, vezi Coada. Coada de așteptare este o structură de date cu disciplina de acces la elementele "primul venit primul" (FIFO, First In First Out). Adăugarea unui element (de obicei marcat cu cuvântul ... ... Wikipedia
matrice asociativă - (dicționar) de tip abstract de date (interfața la depozitul de date) care stochează perechi de forma „(cheie, valoare)“ și susține operațiunile de adăugare de perechi, și găsirea și eliminarea unei perechi de chei: INSERT (cheie, valoare) FIND ( cheie) ... ... Wikipedia
tabel Hash - Un tabel hash este o structură de date care implementează interfața este un tablou asociativ, care este, vă permite să stocați o pereche (cheie, valoare) și de a efectua trei operații: operația pentru a adăuga o nouă pereche, operațiunea de căutare și operația de îndepărtare o pereche de ... ... Wikipedia
Structura datelor - un arbore binar, un exemplu simplu de structură de date conectată la ramificație. Structura de date (structura de date engleză) este o unitate software care vă permite să stocați date într-o ... Wikipedia
Lista Linked - în informatică, dinamice, legate structura de listă de date de bază constând din noduri, fiecare dintre care conține atât datele reale și una sau două link-ul ( „link-ul“) la alta și / sau lista precedentă nodul [1]. Principalul ... ... Wikipedia
Un arbore binar de căutare - Tipul de timp copac complexitate medie O simbolism În cel mai rău de memorie caz, consumul de O (n) O (n) Căutare O (h) O (n) Introducerea O (h) O (n) îndepărtarea O (h) O (n), unde h este înălțimea unui copac ... Wikipedia
Lista de lacunare - (. Engl Skip List) Structura de date de probabilitate bazate pe mai multe liste de concurente legate sortate cu o eficiență comparabilă cu arborele binar (de ordinul O (log n) timpul mediu pentru cele mai multe operații). La baza ... ... Wikipedia
Articole similare
Trimiteți-le prietenilor: