İkili Karar Diyagramı
Binary Decision Diagram (BDD) · Ayrıca şöyle bilinir: BDD, reduced BDD, ordered BDD
İkili Karar Diyagramları (BDD'ler), Randal Bryant tarafından 1986'da geliştirilen Boole fonksiyonlarının kanonik, hafıza-verimli bir temsilidir. Bir BDD, tüm değişken atamalarını ve sonuçlarını kodlayan yönlendirilmiş döngüsüz bir grafiktir; indirgenmiş BDD'ler her fonksiyon için benzersizdir ve model kontrolünde, devre tasarımında ve sembolik hesaplamada kombinatoryal mantığın verimli manipülasyonunu sağlar.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Ne zaman kullanılır
Boole tatmin edilebilirliği (SAT), sonlu-durumlu sistemlerin model kontrolü, kombinatoryal devre doğrulama ve sembolik durum alanı keşfi için BDD'leri kullan. Fonksiyonun yerelliği veya yapısı olduğunda etkilidir; oldukça düzensiz fonksiyonlardan kaçının (en kötü durum üssel boyut). Modern SAT çözücüler genellikle belirli alt problemler için dahili olarak BDD'leri kullanır.
Güçlü yönler & sınırlılıklar
- Kanonik temsil: her Boole fonksiyonunun benzersiz bir indirgenmiş BDD'si vardır (verilen değişken sıralaması), verimli eşitlik kontrolünü sağlar
- Kompakt depolama: birçok pratik fonksiyon, üssel değişkenlere rağmen polinomsal BDD boyutuna sahiptir
- Verimli işlemler: Boole işlemleri (VE, VEYA, DEĞİL, niceleme) O(|BDD₁| × |BDD₂|) zamanda yürütülür
- Tam algoritma: durum alanını sistematik olarak keşfeder; ulaşılamazlığı ve kilitlenme özgürlüğünü kanıtlayabilir
- Değişken sıralaması kritiktir: kötü sıralama üssel boyut şişmesine neden olabilir; optimal sırayı bulmak NP-zor
- Hafıza patlaması: düşmanca seçilmiş fonksiyonlar (örneğin, orta-bit fonksiyonu) doğası gereği üssel BDD boyutuna sahiptir
- Aritmetik için uygun değildir: tamsayı aritmetiği, işlemlerin Boole temsilini gerektirir, bu da devasa BDD'lere yol açar
- Hata ayıklama zorluğu: BDD boyutu değişiklikleri öngörülemez; yeniden sıralama sezgileri probleme özgüdür
SSS
Değişken sıralaması nedir ve neden bu kadar önemlidir?
Değişken sıralaması, değişkenlerin kökten terminale doğru test edildiği sıradır (örneğin, x₁, x₂, x₃, …). Aynı fonksiyon, A sırası için BDD boyutuna 10, B sırası için ise 10^6 sahip olabilir. Dinamik yeniden sıralama (Sift), boyutu en aza indirmek için bitişik değişkenleri açgözlüce değiştirir; ilgili değişkenleri gruplama gibi sezgiler yardımcı olur.
BDD yapısındaki indirgeme adımı nedir?
f = (¬x ∧ f₀) ∨ (x ∧ f₁) genişletildikten sonra, gereksiz düğümleri birleştirin: iki düğümün özdeş alt öğeleri varsa, onları birleştirin. Ayrıca yinelenen düğümleri (aynı değişken, aynı alt öğeler) kaldırın. Agresif bir şekilde birleştirme, fonksiyon semantiğini korurken grafiği küçültür.
İki BDD üzerinde nasıl Boole işlemleri (VE, VEYA) gerçekleştirilir?
Özyinelemeli algoritma: VE(BDD₁, BDD₂) her iki grafiği eşzamanlı olarak dolaşır, yalnızca her iki yol da 1'e ulaşırsa terminal 1'i döndürür, aksi takdirde 0. Yinelenen özyinelemeyi önlemek için alt problemleri önbelleğe alın. Zaman O(|BDD₁| × |BDD₂|)'dir; sonuç boyutu girdi yapısına göre değişir.
BDD boyutu ne zaman çözülemez hale gelir ve alternatifleri nelerdir?
'Orta bit' (parite benzeri) gibi fonksiyonlar üssel BDD boyutuna sahiptir. Alternatifler: ZDD'ler (sıfır-baskılanmış), SAT çözücüler (açık yapıyı önleyin), bit-vektör teorili SMT çözücüler veya alana özgü araçlar. Hibrit yaklaşımlar (yapı için BDD, aritmetik için SAT) genellikle saf BDD'nin başarısız olduğu durumlarda başarılı olur.
Kaynaklar
- Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 677–691. DOI: 10.1109/TC.1986.1676819 ↗
- Andersen, H. R. (1997). An introduction to binary decision diagrams. Technical Report, IT University of Copenhagen. link ↗
- Becker, B., & Drechsler, R. (1998). Binary Decision Diagrams: Theory and Implementation. Kluwer. ISBN: 0792380185
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Binary Decision Diagram (BDD). ScholarGate. https://scholargate.app/tr/numerical-methods/binary-decision-diagram