İkili karar diyagramı

Bilgisayar biliminde, ikili karar diyagramı (BDD) veya dallanma programı, bir veri yapısı olup Boolean fonksiyonunu temsil etmek için kullanılır. Daha soyut bir düzeyde, BDD’ler kümelerin veya ilişkilerin sıkıştırılmış bir gösterimi olarak düşünülebilir. Diğer sıkıştırılmış gösterimlerden farklı olarak, işlemler sıkıştırılmış hali üzerinde doğrudan, yani açılmadan gerçekleştirilir.

Benzer veri yapıları arasında negation normal form (NNF), Zhegalkin polinomları ve önerme yönlendirilmiş döngüsüz grafikler (PDAG) bulunur.

Tanım

Bir Boolean fonksiyonu, köklü, yönlendirilmiş, döngüsüz bir graf olarak temsil edilebilir. Bu grafik, birkaç (karar) düğümü ve iki terminal düğümden oluşur. İki terminal düğüm 0 (FALSE) ve 1 (TRUE) olarak etiketlenir. Her (karar) düğümü $u$, bir Boolean değişkeni $x_{i}$ ile etiketlenir ve iki alt düğüme sahiptir; bunlar düşük alt düğüm (low child) ve yüksek alt düğüm (high child) olarak adlandırılır. Düğüm $u$'den düşük (veya yüksek) alt düğüme giden kenar, değişken $x_{i}$'ye FALSE (veya sırasıyla TRUE) değeri atanmasını temsil eder. Böyle bir BDD, kökten tüm yollarda değişkenlerin aynı sırayla yer alması durumunda 'sıralı' (ordered) olarak adlandırılır. Bir BDD'nin 'azaltılmış' (reduced) olması için aşağıdaki iki kural uygulanmış olmalıdır:

• İzomorfik alt grafikleri birleştir.
• İki alt düğümü izomorfik olan herhangi bir düğümü kaldır.

Günlük kullanımda, BDD terimi neredeyse her zaman Azaltılmış Sıralı İkili Karar Diyagramı (literatürde ROBDD olarak anılır; sıralama ve azaltma özellikleri vurgulanmak istendiğinde kullanılır) anlamına gelir. ROBDD'nin avantajı, belirli bir fonksiyon ve değişken sırası için kanonik (izomorfizme kadar benzersiz) olmasıdır. Bu özellik, fonksiyonel eşdeğerlik kontrolü ve fonksiyonel teknoloji eşlemesi gibi işlemlerde faydalıdır.

Kök düğümden 1-terminal düğüme olan bir yol, temsil edilen Boolean fonksiyonunun doğru olduğu (kısmi veya tam) bir değişken atamasını gösterir. Yol, bir düğümden düşük (veya yüksek) alt düğüme ilerledikçe, o düğümün değişkenine 0 (sırasıyla 1) değeri atanmış olur.

Örnek

Aşağıdaki soldaki şekil, bir ikili karar ağacıdır (azaltma kuralları uygulanmamıştır) ve bir doğruluk tablosu, her ikisi de $f(x_{1},x_{2},x_{3})$ fonksiyonunu temsil eder. Soldaki ağaçta, verilen bir değişken ataması için fonksiyonun değeri, grafikteki bir yol izlenerek terminal düğüme ulaşılmasıyla belirlenebilir. Aşağıdaki şekillerde, kesikli çizgiler düşük alt düğüme giden kenarları, düz çizgiler ise yüksek alt düğüme giden kenarları temsil eder. Bu nedenle, $f(0,1,1)$ değerini bulmak için, x₁'den başlayıp kesikli çizgiyle x₂'ye (çünkü x₁ değeri 0’dır), ardından iki düz çizgiyle (çünkü x₂ ve x₃ değerleri 1’dir) ilerlenir. Bu yol, $f(0,1,1)$ değerini veren terminal 1’e ulaşır.

Soldaki ikili karar ağacı, iki azaltma kuralına göre mümkün olduğunca küçültülerek ikili karar diyagramına dönüştürülebilir. Ortaya çıkan BDD, sağdaki şekilde gösterilmiştir.

Fonksiyon $f(x_{1},x_{2},x_{3})=(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})$ için ikili karar ağacı ve doğruluk tablosu. Fonksiyon, Boolean operatörleri notasyonuyla ifade edilmiştir.

f fonksiyonu için BDD

Bu Boolean fonksiyonunu yazmak için diğer bir gösterim ise ${\overline {x}}_{1}{\overline {x}}_{2}{\overline {x}}_{3}+x_{1}x_{2}+x_{2}x_{3}$ şeklindedir.

Terslenmiş kenarlar

Terslenmiş kenarlar kullanılarak ikili karar diyagramının gösterimi

Bir ROBDD, terslenmiş kenarlar olarak da bilinen tamamlayıcı bağlantılar kullanılarak daha da kompakt şekilde temsil edilebilir veya imzalı BDD olarak adlandırılır.

Terslenmiş kenarlar, düşük kenarların terslenmiş olup olmadığının belirtilmesiyle oluşturulur. Eğer bir kenar terslenmişse, bu kenar, kenarın işaret ettiği düğümün karşılık geldiği Boolean fonksiyonunun olumsuzuna (yani BDD'nin kökü o düğüm olan Boolean fonksiyonunun negasyonuna) işaret eder. Yüksek kenarlar terslenmez; böylece elde edilen BDD gösteriminin kanonik form olması sağlanır. Bu gösterimde, aşağıda açıklanan nedenlerle BDD'lerin tek bir yaprak düğümü vardır.

BDD’leri terslenmiş kenarlarla temsil etmenin iki avantajı vardır:

Bir BDD’nin negasyonunu hesaplamak sabit zamanda yapılabilir. Bellek kullanımı (yani gereken hafıza) en fazla iki kat daha azdır. Ancak, Knuth bu görüşe katılmamaktadır:

Tüm büyük BDD paketleri bu tür bağlantıları kullansa da, bilgisayar programlarının çok daha karmaşık hale gelmesi nedeniyle önerilmesi zordur. Bellek tasarrufu genellikle ihmal edilebilir düzeydedir ve hiçbir zaman iki katından daha iyi değildir; ayrıca yazarın deneyleri çalışma süresinde çok az kazanç sağladığını göstermektedir.

Bu gösterimde bir BDD’ye yapılan referans, (muhtemelen terslenmiş) BDD köküne işaret eden bir "kenar"dır. Bu, terslenmiş kenarların kullanılmadığı gösterimde bir BDD’ye yapılan referansın BDD’nin kök düğümü olmasıyla tezat oluşturur. Bu gösterimde referansın bir kenar olması gerekir. Çünkü her Boolean fonksiyon için, fonksiyon ve onun negasyonu, aynı BDD’nin köküne giden bir kenar ve terslenmiş bir kenar ile temsil edilir. İşte bu yüzden negasyon sabit zamanda gerçekleşir. Ayrıca, tek bir yaprak düğümün yeterli olmasının sebebini de açıklar: FALSE, yaprak düğüme işaret eden terslenmiş bir kenar ile; TRUE ise yaprak düğüme işaret eden normal (terslenmemiş) bir kenar ile temsil edilir.

Örneğin, bir Boolean fonksiyonunun, terslenmiş kenarlarla temsil edilen bir BDD ile gösterildiğini varsayalım. Değişkenlere verilen (Boolean) değerler için fonksiyonun değerini bulmak üzere, BDD’nin köküne işaret eden referans kenarından başlanır ve verilen değişken değerlerine göre tanımlanan yol izlenir (bir düğümü etiketleyen değişken FALSE ise düşük kenar, TRUE ise yüksek kenar takip edilir) ve yaprak düğüme ulaşılır. Bu yol boyunca kaç tane terslenmiş kenar geçtiğimiz sayılır. Yaprak düğüme ulaşıldığında, eğer geçilen terslenmiş kenar sayısı tek ise, verilen değişken ataması için Boolean fonksiyonunun değeri FALSE olur; çift ise TRUE olur.

Bu gösterimdeki bir BDD örneği sağdaki şekilde verilmiştir ve yukarıdaki diyagramlarda gösterilen aynı Boolean ifadesini temsil eder (yani $(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})$). Düşük kenarlar kesikli çizgilerle, yüksek kenarlar düz çizgilerle; terslenmiş kenarlar ise kaynaklarında bir daire ile gösterilmiştir. @ sembollü düğüm, BDD’ye referansı temsil eder; yani referans kenarı bu düğümden başlayan kenardır.