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

एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-सीमान्त बाइनरी डिसीजन डायग्राम, एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है बाइनरी डिसीजन डायग्राम, या साहित्य में सामान्यतः बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो सीमान्त बिंदु बूलियन वैल्यू 0 (फॉल्स) और 1 (ट्रू) तक सीमित नहीं हैं। सीमान्त बिंदु स्थिरांक 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-किनारे जो कि मान ट्रू के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए फॉल्स का प्रतिनिधित्व करता है।

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

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

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

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

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

अनुप्रयोग

ADDs को सबसे पहले विरल मैट्रिक्स गुणन और सबसे छोटे पथ एल्गोरिदम के लिए प्रयुक्त किया गया था।

यह भी देखें

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