Dijagram binarnog momenta

Izvor: Wikipedia

Dijagram binarnog momenta (eng. BMD) je generalizacija binarnog dijagrama odlučivanja (eng. BDD) na linearne funkcije preko domena kao što su logičke, ali takođe na cele brojeve ili na realne brojeve.

Oni mogu da se bave sa Bulovim funkcijama složenosti sličnoj BDD-u, ali takođe neke funkcije se ne bave veoma efikasno sa BDD, dok lako rukuju sa BMD.

Najvažnija karakteristika BMD-a je da kao i BDD svaka funkcija ima tačno jednu kanonsku reprezentaciju, i mnoge operacije se mogu efikasno izvesti na ovim reprezentacijama.

Glavna mogućnost koja diferencira BMD od BDD-a je korišćenje linearnih umesto "pointwise" dijagrama, i imanje težinskih ivica.

Pravila koja obezbeđuju kanoničnost reprezentacije su :

  • Odluka preko promenjivih većih u poretku mogu samo da pokazuju na odluke preko promenjivih manjih u poretku.
  • Ni jedna dva čvora ne smeju biti identična
  • Ni jedan čvor ne može imati sve delove odluke ekvivalentne nuli.
  • Ni jedna ivica ne sme da ima težinu nula. (sve takve ivice bi trebalo zameniti direktim vezama u 0 )
  • Težine ivica bi trebalo da se komprimuju. Bez ovog pravila ili nekog pravila njemu ekvivalentnom, bilo bi mogiće za funkciju da ima vise reprezentacija.

Odvojeni i linearna dekompozicija[uredi - уреди]

U odvojenoj dekompoziciji kao u BDD-u, na svaku granu mi čuvamo rezultat svih grana odvojeno. Primer takve dekompozicije za celobrojnu funkciju (2x + y) je :

\begin{cases} \text{if } x
\begin{cases}
 \text{if } y , 3
\\
 \text{if } \neg y , 2
\end{cases}
\\ 
 \text{if } \neg x
\begin{cases}
 \text{if } y \text{ , } 1
\\
 \text{if } \neg y \text{ , } 0
\end{cases}
\end{cases}

U linearnoj dekompoziciji mi dajemo umesto podrazumevane vrednosti i razlike:

\begin{cases}
\text{always} 
\begin{cases}
\text{always } 0 \\
\text{if } y , +1
\end{cases}
\\
\text{if } x , +2
\end{cases}

Lako se može uočiti da je linearna reprezentacija mnogo efikasnija i slučaju aditivnih funkcija, kao kad dodamo mnoge elemente, reprezentacija će imati samo O(n) elemenata, dok prethodna, čak sa deljenjem eksponencijalno mnogo.

Težine ivica[uredi - уреди]

Još jedno produženje je korišćenje težina za ivice. Vrednost funkcije u datom čvoru je zbir tačnih čvorova ispod njega puta težina ivica. Na primer (4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0) se može reprezentovati kao :

  1. Rezultujuci cvor, uvek 1× vrednost čvora 2, ako x_2 dodaj 4× vrednost čvora četiri.
  2. Uvek 1× vrednost čvora 3, ako x_1 dodaj 2× vrednost čvora četiri.
  3. Uvek 0, ako x_0 dodaj 1× vrednost čvora 4.
  4. Uvek 1× vrednost čvora 5, ako y_2 dodaj +4.
  5. Uvek 1× vrednost čvora 6, ako y_1 dodaj +2.
  6. Uvek 0, ako y_0 dodaj +1.

Bez težinskih čvorova, mnogo kompleksnija reprezentacija bi bila potrebna :

  1. Rezultujuci čvor, uvek vrednost čvora 2, ako x_2 vrednost čvora 4.
  2. Uvek vrednost čvora 3, ako x_1 vrednost čvora 7.
  3. Uvek 0, ako x_0 vrednost čvora 10.
  4. Uvek vrednost čvora 5, ako y_2 dodaj +16.
  5. Uvek vrednost čvora 6, ako y_1 dodaj +8.
  6. Uvek 0, ako y_0 dodaj +4.
  7. Uvek vrednost čvora 8, ako y_2 dodaj +8.
  8. Uvek vrednost čvora 9, ako y_1 doda +4.
  9. Uvek 0, ako y_0 dodaj +2.
  10. Uvek vrednost čvora 11, ako y_2 dodaj +4.
  11. Uvek vrednost čvora 12, ako y_1 dodaj +2.
  12. Uvek 0, ako y_0 dodaj +1