Dijagram binarnog momenta

Iz Wikipedije, slobodne enciklopedije

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 - уреди | uredi izvor]

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 :

U linearnoj dekompoziciji mi dajemo umesto podrazumevane vrednosti i razlike:

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 - уреди | uredi izvor]

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 se može reprezentovati kao :

  1. Rezultujuci cvor, uvek 1× vrednost čvora 2, ako dodaj 4× vrednost čvora četiri.
  2. Uvek 1× vrednost čvora 3, ako dodaj 2× vrednost čvora četiri.
  3. Uvek 0, ako dodaj 1× vrednost čvora 4.
  4. Uvek 1× vrednost čvora 5, ako dodaj +4.
  5. Uvek 1× vrednost čvora 6, ako dodaj +2.
  6. Uvek 0, ako dodaj +1.

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

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