Binární momentový diagram - Binary moment diagram - Wikipedia

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Binární momentový diagram"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Leden 2007) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A binární momentový diagram (BMD) je zobecněním binární rozhodovací diagram (BDD) na lineární funkce přes domény, jako jsou booleovy (jako BDD), ale také na celá čísla nebo na reálná čísla.

Mohou se vypořádat s booleovskými funkcemi se složitostí srovnatelnou s BDD, ale také některé funkce, které jsou v BDD řešeny velmi neefektivně, snadno zvládne BMD, zejména násobení.

Nejdůležitější vlastnosti BMD spočívají v tom, že stejně jako u BDD má každá funkce přesně jednu kanonickou reprezentaci a na těchto reprezentacích lze efektivně provádět mnoho operací.

Hlavní rysy, které odlišují BMD od BDD, jsou použití lineárních namísto bodových diagramů a vážené hrany.

Pravidla, která zajišťují kanoničnost zastoupení, jsou:

• Rozhodování nad proměnnými vyššími v objednávce může ukazovat pouze na rozhodnutí nad proměnnými nižšími v objednávce.
• Žádné dva uzly nemusí být identické (v normalizaci by měly být všechny odkazy na jeden z těchto uzlů nahrazeny odkazy na jiné)
• Žádný uzel nemusí mít všechny rozhodovací části ekvivalentní 0 (odkazy na takové uzly by měly být nahrazeny odkazy na jejich vždy část)
• Žádná hrana nemusí mít nulovou váhu (všechny takové hrany by měly být nahrazeny přímými odkazy na 0)
• Váhy okrajů by měly být coprime. Bez tohoto pravidla nebo jeho ekvivalentu by bylo možné, aby funkce měla mnoho reprezentací, například 2X + 2 lze vyjádřit jako 2 · (1 +X) nebo 1 · (2 ​​+ 2X).

Bodový a lineární rozklad

V bodovém rozkladu, stejně jako v BDD, ukládáme v každém bodě větve výsledek všech větví samostatně. Příklad takového rozkladu pro celočíselnou funkci (2X + y) je:

${ displaystyle { begin {cases} { text {if}} x { begin {cases} { text {if}} y, 3 { text {if}} neg y, 2 end { případy}} { text {if}} neg x { begin {cases} { text {if}} y { text {,}} 1 { text {if}} neg y { text {,}} 0 end {cases}} end {cases}}}$

V lineárním rozkladu místo toho poskytujeme výchozí hodnotu a rozdíl:

${ displaystyle { begin {cases} { text {always}} { begin {cases} { text {always}} 0 { text {if}} y, + 1 end {cases}} { text {if}} x, + 2 end {případy}}}$

Je snadno vidět, že druhá (lineární) reprezentace je mnohem efektivnější v případě aditivních funkcí, protože když přidáme mnoho prvků, druhá reprezentace bude mít pouze O (n) prvky, zatímco první (bodové), i při sdílení, exponenciálně mnoho.

Závaží hran

Dalším rozšířením je použití závaží pro hrany. Hodnota funkce v daném uzlu je součtem skutečných uzlů pod ním (uzel pod vždy a případně rozhodnutý uzel) krát váhy hran.

Například, ${ displaystyle (4x_ {2} + 2x_ {1} + x_ {0}) (4y_ {2} + 2y_ {1} + y_ {0})}$ lze reprezentovat jako:

1. Výsledný uzel, vždy 1 × hodnota uzlu 2, pokud ${ displaystyle x_ {2}}$ přidat 4 × hodnotu uzlu 4
2. Vždy 1 × hodnota uzlu 3, pokud ${ displaystyle x_ {1}}$ přidat 2 × hodnotu uzlu 4
3. Vždy 0, pokud ${ displaystyle x_ {0}}$ přidat 1 × hodnotu uzlu 4
4. Vždy 1 × hodnota uzlu 5, pokud ${ displaystyle y_ {2}}$ přidat +4
5. Vždy 1 × hodnota uzlu 6, pokud ${ displaystyle y_ {1}}$ přidat +2
6. Vždy 0, pokud ${ displaystyle y_ {0}}$ přidat +1

Bez vážených uzlů by bylo zapotřebí mnohem složitější reprezentace:

1. Výsledný uzel, vždy hodnota uzlu 2, pokud ${ displaystyle x_ {2}}$ hodnota uzlu 4
2. Vždy hodnota uzlu 3, pokud ${ displaystyle x_ {1}}$ hodnota uzlu 7
3. Vždy 0, pokud ${ displaystyle x_ {0}}$ hodnota uzlu 10
4. Vždy hodnota uzlu 5, pokud ${ displaystyle y_ {2}}$ přidat +16
5. Vždy hodnota uzlu 6, pokud ${ displaystyle y_ {1}}$ přidat +8
6. Vždy 0, pokud ${ displaystyle y_ {0}}$ přidat +4
7. Vždy hodnota uzlu 8, pokud ${ displaystyle y_ {2}}$ přidat +8
8. Vždy hodnota uzlu 9, pokud ${ displaystyle y_ {1}}$ přidat +4
9. Vždy 0, pokud ${ displaystyle y_ {0}}$ přidat +2
10. Vždy hodnota uzlu 11, pokud ${ displaystyle y_ {2}}$ přidat +4
11. Vždy hodnota uzlu 12, pokud ${ displaystyle y_ {1}}$ přidat +2
12. Vždy 0, pokud ${ displaystyle y_ {0}}$ přidat +1

Reference