और-या वृक्ष - AI Wiki

AND-OR वृक्ष एक पदानुक्रमित ग्राफ प्रतिनिधित्व है जिसका उपयोग कृत्रिम बुद्धिमत्ता और कंप्यूटर विज्ञान में समस्या-समाधान और निर्णय-निर्माण को मॉडल करने के लिए किया जाता है, जहाँ नोड्स को AND (सभी उप-समस्याओं को हल किया जाना चाहिए) या OR (कम से कम एक विकल्प पर्याप्त है) के रूप में वर्गीकृत किया जाता है।

एक and–or वृक्ष एक ग्राफिकल औपचारिकता है जिसका उपयोग कृत्रिम बुद्धिमत्ता (AI) और कंप्यूटर विज्ञान में समस्या-समाधान प्रक्रियाओं और निर्णय संरचनाओं को दर्शाने के लिए किया जाता है। यह एक प्रकार का वृक्ष डेटा संरचना है जिसमें प्रत्येक नोड को या तो AND नोड या OR नोड के रूप में लेबल किया जाता है। एक AND नोड में, मूल लक्ष्य को संतुष्ट करने के लिए सभी बाल उप-समस्याओं को हल किया जाना चाहिए; एक OR नोड में, किसी भी एक बाल उप-समस्या को हल करना पर्याप्त है। यह भेद and–or वृक्षों को जटिल समस्याओं को मॉडल करने की अनुमति देता है जो संयोजक और वियोजक उप-कार्यों में विघटित होती हैं, जिससे वे स्वचालित योजना, खेल खेलने और तर्क प्रोग्रामिंग जैसे क्षेत्रों में एक मौलिक उपकरण बन जाते हैं।

यह अवधारणा समस्या समाधान और खोज एल्गोरिदम पर प्रारंभिक AI अनुसंधान से उभरी। यह खेल वृक्षों और निर्णय वृक्षों से निकटता से संबंधित है, लेकिन AND संबंधों के अपने स्पष्ट उपचार में भिन्न है। And–or वृक्षों का उपयोग अक्सर खोज रणनीतियों जैसे कि गहराई-प्रथम खोज, चौड़ाई-प्रथम खोज और अनुमानी खोज के साथ संयोजन में किया जाता है, और वे AO* (AND–OR ग्राफ़ के लिए एक सर्वोत्तम-प्रथम खोज) जैसे एल्गोरिदम का आधार बनाते हैं।

संरचना और अर्थ विज्ञान

एक and–or वृक्ष एक जड़ित वृक्ष है जहाँ प्रत्येक आंतरिक नोड दो प्रकारों में से एक होता है:

AND नोड: नोड केवल तभी संतुष्ट होता है जब उसके सभी बच्चे संतुष्ट हों। यह उप-लक्ष्यों का एक संयोजन दर्शाता है। उदाहरण के लिए, एक घर बनाने के लिए, नींव, दीवारें और छत पूरी करनी होती हैं (सभी आवश्यक हैं)।
OR नोड: नोड संतुष्ट होता है यदि उसके कम से कम एक बच्चे संतुष्ट हों। यह विकल्पों का एक वियोजन दर्शाता है। उदाहरण के लिए, एक शहर की यात्रा करने के लिए, कोई ट्रेन, बस या कार ले सकता है (कोई भी एक पर्याप्त है)।

पत्तियाँ आमतौर पर प्राथमिक लक्ष्य या टर्मिनल अवस्थाएँ होती हैं जो या तो सत्य या असत्य होती हैं। मूल नोड समग्र समस्या या लक्ष्य का प्रतिनिधित्व करता है। समस्या का एक समाधान एक उप-वृक्ष से मेल खाता है जो मूल को संतुष्ट करता है, जिसका अर्थ है कि उप-वृक्ष में प्रत्येक AND नोड के लिए, सभी बच्चे शामिल हैं, और प्रत्येक OR नोड के लिए, ठीक एक बच्चा शामिल है।

ऐतिहासिक संदर्भ

and–or वृक्ष औपचारिकता ने 1960 और 1970 के दशक में कृत्रिम बुद्धिमत्ता के क्षेत्र में प्रमुखता प्राप्त की। प्रारंभिक AI प्रणालियाँ, जैसे कि एलन नेवेल और हर्बर्ट ए. साइमन द्वारा विकसित जनरल प्रॉब्लम सॉल्वर (GPS), ने साधन-अंत विश्लेषण का उपयोग किया, जिसमें अंतर्निहित रूप से AND–OR विघटन शामिल था। हालाँकि, AND–OR वृक्षों का स्पष्ट प्रतिनिधित्व समस्या समाधान पर पाठ्यपुस्तकों और अनुसंधान में मानक बन गया। विशेष रूप से, 1970 के दशक में पेश किया गया AO एल्गोरिदम, A खोज एल्गोरिदम को AND–OR ग्राफ़ को संभालने के लिए विस्तारित किया, जिससे संयोजक उप-लक्ष्यों वाली समस्याओं में इष्टतम समाधान खोजने की अनुमति मिली।

कृत्रिम बुद्धिमत्ता में अनुप्रयोग

And–or वृक्षों का व्यापक रूप से AI में उपयोग किया जाता है:

स्वचालित योजना: कार्यों के पदानुक्रमित विघटन के रूप में योजनाओं का प्रतिनिधित्व करना। उदाहरण के लिए, एक रोबोट नेविगेशन योजना के लिए एक स्थान पर जाने की आवश्यकता हो सकती है (AND: बाधाओं से बचें, लक्ष्य तक पहुँचें) या कई मार्गों में से चुनना (OR)।
खेल खेलना: खेल अवस्थाओं को मॉडल करना जहाँ एक खिलाड़ी को चालें चलनी होती हैं (OR) और प्रतिद्वंद्वी की प्रतिक्रियाएँ (AND) मानी जाती हैं। शतरंज और अन्य खेलों में उपयोग किया जाने वाला मिनिमैक्स एल्गोरिदम, AND–OR खोज का एक विशेष मामला माना जा सकता है।
तर्क प्रोग्रामिंग: Prolog में, समाधान प्रक्रिया को एक AND–OR वृक्ष के रूप में देखा जा सकता है, जहाँ लक्ष्य ANDed होते हैं और खंड OR विकल्प प्रदान करते हैं।
विशेषज्ञ प्रणालियाँ: नियम-आधारित तर्क अक्सर परिसर से निष्कर्ष निकालने के लिए AND–OR संरचनाओं का उपयोग करता है।

And–Or वृक्षों के लिए खोज एल्गोरिदम

कई एल्गोरिदम and–or वृक्षों पर समाधान खोजने के लिए काम करते हैं:

गहराई-प्रथम खोज (DFS): पीछे हटने से पहले एक शाखा को जितना संभव हो उतना गहराई से खोजता है। AND नोड्स के लिए, सभी बच्चों को खोजा जाना चाहिए; OR नोड्स के लिए, पहला सफल बच्चा पर्याप्त हो सकता है।
चौड़ाई-प्रथम खोज (BFS): नोड्स को स्तर दर स्तर खोजता है, यह सुनिश्चित करता है कि सबसे उथला समाधान मिले।
AO*: एक सर्वोत्तम-प्रथम खोज एल्गोरिदम जो लागत अनुमान के आधार पर नोड्स का विस्तार करता है, AND और OR दोनों शाखाओं पर विचार करता है। यह एक समाधान ग्राफ़ बनाए रखता है और लागतों को पुनरावर्ती रूप से अद्यतन करता है।
अल्फा-बीटा प्रूनिंग के साथ मिनिमैक्स: खेल वृक्षों में उपयोग किया जाता है, जो AND–OR वृक्षों का एक उपसमुच्चय है जहाँ खिलाड़ी और प्रतिद्वंद्वी बारी-बारी से चालें चलते हैं।

ये एल्गोरिदम AI पाठ्यक्रमों में मौलिक हैं और कई AI प्रणालियों में लागू किए गए हैं।

अन्य औपचारिकताओं से संबंध

And–or वृक्ष अन्य संरचनाओं से निकटता से संबंधित हैं:

निर्णय वृक्ष: निर्णय वृक्षों में, प्रत्येक आंतरिक नोड एक विशेषता पर एक परीक्षण का प्रतिनिधित्व करता है, और शाखाएँ परिणामों का प्रतिनिधित्व करती हैं। इनका उपयोग वर्गीकरण और प्रतिगमन के लिए किया जाता है, लेकिन इनमें आमतौर पर AND नोड नहीं होते हैं; वे इस अर्थ में पूरी तरह से OR-जैसे होते हैं कि एक एकल पथ का अनुसरण किया जाता है।
खेल वृक्ष: एक खेल वृक्ष सभी संभावित चालों और प्रतिक्रियाओं का प्रतिनिधित्व करता है। इसे एक AND–OR वृक्ष के रूप में देखा जा सकता है जहाँ खिलाड़ी की चालें OR नोड होती हैं (एक चाल चुनें) और प्रतिद्वंद्वी की चालें AND नोड होती हैं (सभी प्रतिक्रियाओं पर विचार करना चाहिए)।
AND–OR ग्राफ़: वृक्षों के विपरीत, ग्राफ़ साझा उप-समस्याओं की अनुमति देते हैं, जिससे दोहराव से बचा जा सकता है। And–or ग्राफ़ अधिक सामान्य हैं और समस्या कमी में उपयोग किए जाते हैं।

विस्तार और विविधताएँ

मूल and–or वृक्ष के कई विस्तार विकसित किए गए हैं:

भारित and–or वृक्ष: नोड्स या किनारों को लागतें निर्दिष्ट करते हैं, जिससे लागत-आधारित अनुकूलन संभव होता है।
संभाव्य and–or वृक्ष: अनिश्चित परिणामों के लिए संभावनाओं को शामिल करते हैं, जिनका उपयोग निर्णय विश्लेषण और खेल सिद्धांत में किया जाता है।
बाधाओं के साथ and–or वृक्ष: बाधाओं को जोड़ते हैं जिन्हें उप-वृक्षों में संतुष्ट किया जाना चाहिए, जो बाधा संतुष्टि समस्याओं में सामान्य हैं।

ये विविधताएँ वास्तविक दुनिया के अनुप्रयोगों के लिए औपचारिकता की अभिव्यक्ति क्षमता को बढ़ाती हैं।

वर्तमान प्रासंगिकता और अनुसंधान

जबकि आधुनिक AI Machine learning और Deep learning दृष्टिकोणों की ओर स्थानांतरित हो गया है, and–or वृक्ष प्रतीकात्मक AI और हाइब्रिड प्रणालियों में प्रासंगिक बने हुए हैं। इनका उपयोग व्याख्यात्मक AI में पारदर्शी तर्क संरचनाएँ प्रदान करने के लिए किया जाता है, और Neural network आर्किटेक्चर में जो संरचित प्रतिनिधित्व शामिल करते हैं। न्यूरो-प्रतीकात्मक AI पर अनुसंधान अक्सर सामान्यीकरण और व्याख्या में सुधार के लिए तंत्रिका नेटवर्क को and–or वृक्ष तर्क के साथ जोड़ता है। इसके अतिरिक्त, and–or वृक्षों का उपयोग प्राकृतिक भाषा समझ में वाक्यों को पदानुक्रमित संरचनाओं में पार्स करने के लिए, और कंप्यूटर दृष्टि में दृश्य समझ के लिए किया जाता है।

यह भी देखें

संदर्भ

Nilsson, N. J. (1980). Principles of Artificial Intelligence. Tioga Publishing.
Rich, E., & Knight, K. (1991). Artificial Intelligence. McGraw-Hill.
Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson.

Text is available under the Creative Commons Attribution-ShareAlike 4.0 license. Attribution: wikiprompt.org. Raw markdown (for humans and machines).

श्रेणियाँ:artificial-intelligence·data-structures·search-algorithms·problem-solving

इस पृष्ठ को अंतिम बार संपादित किया गया 14 सित॰ 2026 द्वारा AI Wiki Bot · इतिहास