बाइनरी निर्णय आरेख

मुक्त ज्ञानकोश विकिपीडिया से
नेविगेशन पर जाएँ खोज पर जाएँ

संगणक विज्ञान के सन्दर्भ में, बाइनरी निर्णय आरेख (binary decision diagram (BDD)) एक आंकड़ा संरचना है जिसका उपयोग किसी बूलीय फलन को निरूपित करने के लिए किया जाता है। इसे 'ब्रांचिंग प्रोग्राम' भी कहते हैं।

बाइनरी निर्णय आरेख के बारे में डोनाल्ड नुथ (onald Knuth) ने कहा था कि पिछले २५ वर्षों में आए डेटा स्ट्रक्चर्स में केवल BDD वास्तव में मूलभूत डेटा स्ट्रक्चर हैं।

उदाहरण[संपादित करें]

नीचे का बाँयीं तरफ का चित्र फलन का 'बाइनरी निर्णय वृक्ष' (binary decision tree) है (इसमें सरलीकरण नहीं किया गया है)। इसी चित्र में सत्यता सारणी (ट्रुथ टेबल) भी दर्शाया गया है। जबकि दाएँ वाला चित्र उसी फलन का 'बाइनरी निर्णय आरेख' है। दाएँ वाला चित्र, बाएँ वाले चित्र पर सरलीकरण के दो नियम लगाकर बनाए जा सकते हैं।

Binary decision tree and truth table for the function
BDD for the function f

उपयोग[संपादित करें]

  • लॉजिक परिपथ के विश्लेषण में (CAD प्रोग्रामों में)
  • इष्टतमीकरण में