İkili moment diyagramı - Binary moment diagram - Wikipedia

Bir ikili moment diyagramı (BMD) bir genellemedir ikili karar diyagramı (BDD) boole'lar (BDD'ler gibi) gibi etki alanları üzerindeki doğrusal işlevlere, aynı zamanda tam sayılara veya gerçek sayılara.

BDD'lere benzer karmaşıklığa sahip boolean işlevlerle başa çıkabilirler, ancak bir BDD'de çok verimsiz bir şekilde ele alınan bazı işlevler, BMD tarafından kolaylıkla ele alınır, en önemlisi çarpma işlemi.

BMD'nin en önemli özellikleri, BDD'lerde olduğu gibi, her işlevin tam olarak bir kanonik gösterime sahip olması ve bu temsiller üzerinde birçok işlemin verimli bir şekilde gerçekleştirilebilmesidir.

BMD'leri BDD'lerden ayıran ana özellikler, noktasal diyagramlar yerine doğrusal kullanmak ve ağırlıklı kenarlara sahip olmaktır.

Temsilin kanonikliğini sağlayan kurallar şunlardır:

  • Sıralamada daha yüksek olan değişkenlere ilişkin karar, yalnızca sıralamada daha düşük olan değişkenler üzerindeki kararlara işaret edebilir.
  • İki düğüm aynı olamaz (bu tür düğümlerin normalleştirilmesinde, bu düğümlerden birine yapılan tüm referanslar başka bir düğümle değiştirilmelidir)
  • Hiçbir düğüm, 0'a eşdeğer tüm karar bölümlerine sahip olamaz (bu tür düğümlere olan bağlantılar, her zaman bölümlerine ait bağlantılarla değiştirilmelidir)
  • Hiçbir kenarın ağırlığı sıfır olamaz (bu tür tüm kenarlar 0'a doğrudan bağlantılar ile değiştirilmelidir)
  • Kenarların ağırlıkları coprime. Bu kural veya bazı eşdeğerleri olmadan, bir fonksiyonun birçok gösterime sahip olması mümkün olacaktır, örneğin 2x + 2, 2 · (1 +x) veya 1 · (2 ​​+ 2x).

Noktasal ve doğrusal ayrıştırma

Noktasal ayrıştırmada, BDD'lerde olduğu gibi, her dal noktasında tüm dalların sonucunu ayrı ayrı saklıyoruz. Bir tamsayı işlevi için böyle bir ayrıştırma örneği (2x + y) dır-dir:

Doğrusal ayrıştırmada bunun yerine bir varsayılan değer ve bir fark sağlarız:

Kolaylıkla görülebileceği gibi, ikinci (doğrusal) temsil, toplamalı fonksiyonlar durumunda çok daha verimli, çünkü birçok eleman eklediğimizde, ikinci gösterimde sadece O (n) öğeleri, birincisi (noktasal), paylaşımla bile, üssel olarak çok.

Kenar ağırlıkları

Diğer bir uzantı, kenarlar için ağırlık kullanıyor. Verilen düğümdeki bir işlev değeri, altındaki gerçek düğümlerin (her zaman altındaki düğüm ve muhtemelen kararlaştırılan düğüm) çarpı kenarların ağırlıklarının toplamıdır.

Örneğin, şu şekilde temsil edilebilir:

  1. Sonuç düğümü, her zaman 1 × düğüm 2'nin değeri, eğer 4 × düğüm 4 değerini ekle
  2. Her zaman 1 × düğüm 3'ün değeri, eğer 4. düğümün 2 × değerini ekleyin
  3. Her zaman 0, eğer 1 × düğüm 4 değerini ekle
  4. Her zaman 1 × düğüm 5'in değeri, eğer +4 ekle
  5. Her zaman 1 × düğüm 6'nın değeri, eğer +2 ekle
  6. Her zaman 0, eğer +1 ekle

Ağırlıklı düğümler olmadan çok daha karmaşık bir sunum gerekli olacaktır:

  1. Sonuç düğümü, her zaman düğüm 2'nin değeri, eğer 4. düğümün değeri
  2. Her zaman düğüm 3'ün değeri, eğer düğüm 7'nin değeri
  3. Her zaman 0, eğer düğüm 10'un değeri
  4. Her zaman düğüm 5'in değeri, eğer +16 ekle
  5. Her zaman düğüm 6'nın değeri, eğer +8 ekle
  6. Her zaman 0, eğer +4 ekle
  7. Her zaman düğüm 8'in değeri, eğer +8 ekle
  8. Her zaman düğüm 9'un değeri, eğer +4 ekle
  9. Her zaman 0, eğer +2 ekle
  10. Her zaman düğüm 11'in değeri, eğer +4 ekle
  11. Her zaman düğüm 12'nin değeri, eğer +2 ekle
  12. Her zaman 0, eğer +1 ekle

Referanslar