बीजगणितीय निर्णय आरेख: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
== परिभाषा == | == परिभाषा == | ||
ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है <math>\{0,1\}^n</math> स्थिरांक S, या [[बीजगणितीय संरचना]] के वाहक के परिमित समुच्चय के | ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है <math>\{0,1\}^n</math> स्थिरांक S, या [[बीजगणितीय संरचना]] के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई नोड होते हैं। चूंकि, ADD में दो से अधिक टर्मिनल नोड हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं। | ||
एक ADD को फ़ंक्शन के कोडोमेन | एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या [[वेक्टर बूलियन फ़ंक्शन]] के रूप में भी देखा जा सकता है, जैसे कि <math>f: \{0,1\}^n \to Q </math> के साथ <math>S \subseteq Q</math> और <math>card(Q) = 2^n</math> कुछ पूर्णांक n के लिए इसलिए, [[बूलियन बीजगणित]] के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर लागू होते हैं।<ref name=":1" /> | ||
प्रत्येक नोड को एक बूलियन चर द्वारा लेबल किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: एक 1-किनारे जो चर | प्रत्येक नोड को एक बूलियन चर द्वारा लेबल किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: एक 1-किनारे जो कि मान TRUE के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए FALSE का प्रतिनिधित्व करता है। | ||
ADD, BDD (या कम किए गए ऑर्डर वाले [[Index.php?title=BDD|BDD]]) के समान कटौती नियमों को नियोजित करता है: | |||
* किसी भी [[ | * किसी भी [[Index.php?title=आइसोमोर्फिक|आइसोमोर्फिक]] सबग्राफ को मर्ज करें, और | ||
* किसी भी नोड को | * ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों। | ||
ADD एक विशेष चर क्रम के अनुसार विहित हैं। | ADD एक विशेष चर क्रम के अनुसार विहित होते हैं। | ||
== मैट्रिक्स विभाजन == | == मैट्रिक्स विभाजन == | ||
Revision as of 13:47, 29 June 2023
एक बीजगणितीय निर्णय आरेख (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 के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए FALSE का प्रतिनिधित्व करता है।
ADD, BDD (या कम किए गए ऑर्डर वाले BDD) के समान कटौती नियमों को नियोजित करता है:
- किसी भी आइसोमोर्फिक सबग्राफ को मर्ज करें, और
- ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों।
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.
