बीजगणितीय निर्णय आरेख
एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-टर्मिनल बाइनरी निर्णय आरेख (MTBDD), एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है बाइनरी डिसीजन डायग्राम, या साहित्य में आमतौर पर बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो टर्मिनल नोड्स बूलियन वैल्यू 0 (FALSE) और 1 (TRUE) तक सीमित नहीं हैं।[1][2] टर्मिनल नोड स्थिरांक S के सेट से कोई भी मान ले सकता है।
परिभाषा
ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है स्थिरांक S, या बीजगणितीय संरचना के वाहक के परिमित समुच्चय के लिए। ADD एक रूटेड, डायरेक्टेड, एसाइक्लिक ग्राफ है, जिसमें BDD की तरह कई नोड होते हैं। हालाँकि, ADD में दो से अधिक टर्मिनल नोड हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं।
एक ADD को फ़ंक्शन के कोडोमेन का विस्तार करके बूलियन फ़ंक्शन या वेक्टर बूलियन फ़ंक्शन के रूप में भी देखा जा सकता है, जैसे कि साथ और कुछ पूर्णांक n के लिए। इसलिए, बूलियन बीजगणित के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर।[1]
प्रत्येक नोड को एक बूलियन चर द्वारा लेबल किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: एक 1-किनारे जो चर के मूल्य TRUE के मूल्यांकन का प्रतिनिधित्व करता है, और इसके मूल्यांकन के लिए FALSE के लिए 0-किनारे।
एक एडीडी बीडीडी (या आरओबीडीडी) के समान कटौती नियमों को नियोजित करता है:
- किसी भी ग्राफ समरूपता सबग्राफ को मर्ज करें, और
- किसी भी नोड को समाप्त करें जिसके दो बच्चे आइसोमोर्फिक हैं।
ADD एक विशेष चर क्रम के अनुसार विहित हैं।
मैट्रिक्स विभाजन
एक AD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।[2][1]
अनुप्रयोग
ADDs को सबसे पहले मैट्रिक्स गुणन और सबसे छोटी पथ समस्या (बेलमैन-फोर्ड एल्गोरिथम | बेलमैन-फोर्ड, बार-बार स्क्वेरिंग, और फ़्लॉइड-वॉर्शल एल्गोरिथम | फ्लॉयड-वॉर्शल प्रक्रियाएँ) के लिए लागू किया गया था।[1]
यह भी देखें
- बाइनरी निर्णय आरेख
- शून्य-दबा हुआ निर्णय आरेख
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Bahar, R.I.; Frohm, E.A.; Gaona, C.M.; Hachtel, G.D.; Macii, E.; Pardo, A.; Somenzi, F. (1993). "बीजगणितीय निर्णय आरेख और उनके अनुप्रयोग". Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) (in English). IEEE Comput. Soc. Press: 188–191. doi:10.1109/iccad.1993.580054. ISBN 0-8186-4490-7. S2CID 43177472.
- ↑ 2.0 2.1 Fujita, M.; McGeer, P.C.; Yang, J.C.-Y. (1997-04-01). "Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation". Formal Methods in System Design (in English). 10 (2): 149–169. doi:10.1023/A:1008647823331. ISSN 1572-8102. S2CID 30494217.
