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

{{Short description|Symbolic boolean function representation, extension of BDDs}}

एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-टर्मिनल बाइनरी निर्णय आरेख (MTBDD), एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक [[Index.php?title=बूलियन फ़ंक्शन|बूलियन फ़ंक्शन]] का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है [[Index.php?title=बाइनरी डिसीजन डायग्राम|बाइनरी डिसीजन डायग्राम]], या साहित्य में  आमतौर पर बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो टर्मिनल नोड्स बूलियन वैल्यू 0 (FALSE) और 1 (TRUE) तक सीमित नहीं हैं।<ref name=":1">{{Cite journal |last1=Bahar |first1=R.I. |last2=Frohm |first2=E.A. |last3=Gaona |first3=C.M. |last4=Hachtel |first4=G.D. |last5=Macii |first5=E. |last6=Pardo |first6=A. |last7=Somenzi |first7=F. |title=बीजगणितीय निर्णय आरेख और उनके अनुप्रयोग|url=https://doi.org/10.1109/ICCAD.1993.580054 |journal=Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) |year=1993 |pages=188–191 |language=en-US |publisher=IEEE Comput. Soc. Press |doi=10.1109/iccad.1993.580054|isbn=0-8186-4490-7 |s2cid=43177472 }}</ref><ref name=":0">{{Cite journal |last1=Fujita |first1=M. |last2=McGeer |first2=P.C. |last3=Yang |first3=J.C.-Y. |date=1997-04-01 |title=Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation |url=https://doi.org/10.1023/A:1008647823331 |journal=Formal Methods in System Design |language=en |volume=10 |issue=2 |pages=149–169 |doi=10.1023/A:1008647823331 |s2cid=30494217 |issn=1572-8102}}</ref> टर्मिनल नोड स्थिरांक S के सेट से कोई भी मान ले सकता है।

== परिभाषा ==

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

एक 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-किनारे जो कि मान TRUE के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए FALSE का प्रतिनिधित्व करता है।

ADD, BDD (या कम किए गए ऑर्डर वाले [[Index.php?title=BDD|BDD]]) के समान कटौती नियमों को नियोजित करता है:

* किसी भी [[Index.php?title=आइसोमोर्फिक|आइसोमोर्फिक]] सबग्राफ को मर्ज करें, और
* ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों।
ADD एक विशेष चर क्रम के अनुसार विहित होते हैं।

== मैट्रिक्स विभाजन ==
एक ADD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।<ref name=":0" /><ref name=":1" />


== अनुप्रयोग ==

ADDs को सबसे पहले विरल [[मैट्रिक्स गुणन]] और सबसे छोटे पथ एल्गोरिदम (बेलमैन-फोर्ड, रिपीटेड स्क्वेरिंग और फ़्लॉइड-वॉर्शल प्रक्रियाओं) के लिए लागू किया गया था।<ref name=":1" />


== यह भी देखें ==

* बाइनरी डिसीजन डायग्राम 
* [[Index.php?title=ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम|ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम]]

==संदर्भ==
{{Reflist}}


[[Category: चित्र]] [[Category: ग्राफ डेटा संरचनाएं]] 



[[Category: Machine Translated Page]]
[[Category:Created On 19/06/2023]]