बीजगणितीय निर्णय आरेख

एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-टर्मिनल बाइनरी निर्णय आरेख (MTBDD), एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है बाइनरी डिसीजन डायग्राम, या साहित्य में आमतौर पर बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो टर्मिनल नोड्स बूलियन वैल्यू 0 (FALSE) और 1 (TRUE) तक सीमित नहीं हैं। टर्मिनल नोड स्थिरांक S के सेट से कोई भी मान ले सकता है।

परिभाषा

ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है $\{0,1\}^{n}$ स्थिरांक S, या बीजगणितीय संरचना के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई नोड होते हैं। चूंकि, ADD में दो से अधिक टर्मिनल नोड हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं।

एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या वेक्टर बूलियन फ़ंक्शन के रूप में भी देखा जा सकता है, जैसे कि $f:\{0,1\}^{n}\to Q$ के साथ $S\subseteq Q$ और $card(Q)=2^{n}$ कुछ पूर्णांक n के लिए इसलिए, बूलियन बीजगणित के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर लागू होते हैं।

प्रत्येक नोड को एक बूलियन चर द्वारा लेबल किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: एक 1-किनारे जो कि मान TRUE के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए FALSE का प्रतिनिधित्व करता है।

ADD, BDD (या कम किए गए ऑर्डर वाले BDD) के समान कटौती नियमों को नियोजित करता है:

• किसी भी आइसोमोर्फिक सबग्राफ को मर्ज करें, और
• ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों।

ADD एक विशेष चर क्रम के अनुसार विहित होते हैं।

मैट्रिक्स विभाजन

एक ADD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।

अनुप्रयोग

ADDs को सबसे पहले विरल मैट्रिक्स गुणन और सबसे छोटे पथ एल्गोरिदम (बेलमैन-फोर्ड, रिपीटेड स्क्वेरिंग और फ़्लॉइड-वॉर्शल प्रक्रियाओं) के लिए लागू किया गया था।

यह भी देखें

• बाइनरी डिसीजन डायग्राम
• ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम