बाइनरी मोमेंट डायग्राम

एक बाइनरी पल आरेख (बीएमडी) बाइनरी निर्णय आरेख (बीडीडी) का एक सामान्यीकरण है जो बूलियन (जैसे बीडीडी) जैसे डोमेन पर रैखिक कार्यों के लिए होता है, लेकिन पूर्णांक या वास्तविक संख्याओं के लिए भी। वे बीडीडी की तुलना में जटिलता के साथ बूलियन समारोह से निपट सकते हैं, लेकिन बीडीडी में बहुत ही अक्षमता से निपटाए जाने वाले कुछ कार्यों को बीएमडी द्वारा आसानी से नियंत्रित किया जाता है, विशेष रूप से गुणन।

बीएमडी का सबसे महत्वपूर्ण गुण यह है कि, बीडीडी की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।

बीएमडी को बीडीडी से अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के अतिरिक्त रैखिक का उपयोग करना और भारित किनारों का होना है।

प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:

• क्रम में उच्चतर चर पर निर्णय केवल क्रम में नीचे वाले चर पर निर्णय की ओर इशारा कर सकता है।
• कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
• किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके सदैव भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
• किसी भी किनारे का भार शून्य नहीं हो सकता है (ऐसे सभी किनारों को 0 के सीधे लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
• किनारों का वजन सह अभाज्य होना चाहिए। इस नियम या इसके समकक्ष के बिना, एक फ़ंक्शन के लिए कई प्रतिनिधित्व करना संभव होगा, उदाहरण के लिए 2x + 2 को 2·· (1 + x) या 1 · (2 + 2x) के रूप में दर्शाया जा सकता है।

बिंदुवार और रैखिक अपघटन

बिंदुवार अपघटन में, बीडीडी की तरह, प्रत्येक शाखा बिंदु पर हम सभी शाखाओं के परिणाम अलग-अलग संग्रहीत करते हैं। पूर्णांक फ़ंक्शन (2x + y) के लिए ऐसे अपघटन का एक उदाहरण है:

${\begin{cases}{\text{if }}x{\begin{cases}{\text{if }}y,3\\{\text{if }}\neg y,2\end{cases}}\\{\text{if }}\neg x{\begin{cases}{\text{if }}y{\text{ , }}1\\{\text{if }}\neg y{\text{ , }}0\end{cases}}\end{cases}}$

रैखिक अपघटन में हम इसके अतिरिक्त एक डिफ़ॉल्ट मान और एक अंतर प्रदान करते हैं:

${\begin{cases}{\text{always}}{\begin{cases}{\text{always }}0\\{\text{if }}y,+1\end{cases}}\\{\text{if }}x,+2\end{cases}}$

यह आसानी से देखा जा सकता है कि योगात्मक कार्यों के मामले में बाद वाला (रैखिक) प्रतिनिधित्व बहुत अधिक कुशल है, क्योंकि जब हम कई तत्वों को जोड़ते हैं तो बाद वाले प्रतिनिधित्व में केवल O(n) तत्व होंगे, जबकि पूर्व (बिंदुवार), साझा करने के साथ भी , घातीय रूप से कई।

एज वेट

एक अन्य विस्तार किनारों के लिए वज़न का उपयोग करना है। दिए गए नोड पर फ़ंक्शन का मान इसके नीचे के वास्तविक नोड्स (सदैव के तहत नोड, और संभवतः तय किए गए नोड) के किनारों के वजन का योग है।

उदाहरण के लिए, $(4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})$ के रूप में प्रतिनिधित्व किया जा सकता है:

1. परिणाम नोड, सदैव 1 × नोड 2 का मान, यदि $x_{2}$ नोड 4 का 4× मान जोड़ें
2. नोड 3 का सदैव 1× मान, यदि $x_{1}$ नोड 4 का 2× मान जोड़ें
3. सदैव 0, यदि $x_{0}$ नोड 4 का 1× मान जोड़ें
4. सदैव 1× नोड 5 का मान, यदि $y_{2}$ +4 जोड़ें
5. सदैव 1 × नोड 6 का मान, यदि $y_{1}$ +2 जोड़ें
6. सदैव 0, यदि $y_{0}$ +1 जोड़ें

भारित नोड्स के बिना अधिक जटिल प्रतिनिधित्व की आवश्यकता होगी:

1. परिणाम नोड, सदैव नोड 2 का मान, यदि $x_{2}$ नोड 4 का मान
2. सदैव नोड 3 का मान, यदि $x_{1}$ नोड 7 का मान
3. सदैव 0, यदि $x_{0}$ नोड 10 का मान
4. सदैव नोड 5 का मान, यदि $y_{2}$ +16 जोड़ें
5. सदैव नोड 6 का मान, यदि $y_{1}$ +8 जोड़ें
6. सदैव 0, यदि $y_{0}$ +4 जोड़ें
7. सदैव नोड 8 का मान, यदि $y_{2}$ +8 जोड़ें
8. सदैव नोड 9 का मान, यदि $y_{1}$ +4 जोड़ें
9. सदैव 0, यदि $y_{0}$ +2 जोड़ें
10. सदैव नोड 11 का मान, यदि $y_{2}$ +4 जोड़ें
11. सदैव नोड 12 का मान, यदि $y_{1}$ +2 जोड़ें
12. सदैव 0, यदि $y_{0}$ +1 जोड़ें