B*
कंप्यूटर विज्ञान में, बी * (उच्चारण "बी स्टार") एक सर्वश्रेष्ठ-प्रथम ग्राफ खोज एल्गोरिथ्म है जो किसी दिए गए प्रारंभिक नोड से किसी भी लक्ष्य नोड (एक या अधिक संभावित लक्ष्यों में से) तक कम से कम लागत वाला मार्ग ढूंढता है। पहली बार 1979 में हंस बर्लिनर द्वारा प्रकाशित, यह ए * खोज एल्गोरिदम से संबंधित है। सारांश एल्गोरिथ्म एकल बिंदु-मूल्यवान अनुमानों के विपरीत पेड़ के नोड्स के लिए अंतराल संग्रहीत करता है। फिर, पेड़ के पत्ती के नोड्स को तब तक खोजा जा सकता है जब तक कि शीर्ष स्तर के नोड्स में से एक का अंतराल स्पष्ट रूप से "सबसे अच्छा" न हो। विवरण बी *-ट्री के लीफ नोड्स के अनुमानों के बजाय अंतराल मूल्यांकन दिए जाते हैं जो एकल संख्या के बजाय अंतराल होते हैं। अंतराल में उस नोड का सही मान होना चाहिए। यदि लीफ नोड्स से जुड़े सभी अंतराल इस गुण को संतुष्ट करते हैं, तो बी * लक्ष्य अवस्था के लिए एक इष्टतम मार्ग की पहचान करेगा। बैक-अप प्रक्रिया पेड़ के भीतर अंतराल का समर्थन करने के लिए, माता-पिता की ऊपरी सीमा को बच्चों की अधिकतम ऊपरी सीमा के लिए निर्धारित किया जाता है। माता-पिता की निचली सीमा बच्चों की निचली सीमा की अधिकतम सीमा पर निर्धारित की जाती है। ध्यान दें कि अलग-अलग बच्चे इन सीमाओं की आपूर्ति कर सकते हैं। खोज बी * की समाप्ति व्यवस्थित रूप से "पृथक्करण" बनाने के लिए नोड्स का विस्तार करती है, जो तब होती है जब जड़ के प्रत्यक्ष बच्चे की निचली सीमा कम से कम जड़ के किसी अन्य प्रत्यक्ष बच्चे की ऊपरी सीमा जितनी बड़ी होती है। एक पेड़ जो जड़ में अलगाव पैदा करता है, उसमें इस बात का प्रमाण होता है कि सबसे अच्छा बच्चा कम से कम किसी भी अन्य बच्चे की तरह अच्छा है। व्यवहार में, जटिल खोज व्यावहारिक संसाधन सीमाओं के भीतर समाप्त नहीं हो सकती हैं। इसलिए एल्गोरिथ्म को आम तौर पर समय या स्मृति सीमा जैसे कृत्रिम समाप्ति मानदंडों के साथ संवर्धित किया जाता है। जब एक कृत्रिम सीमा तय की जाती है, तो आपको इस बारे में एक शोधात्मक निर्णय लेना चाहिए कि किस कदम का चयन करना है। आम तौर पर, पेड़ आपको रूट नोड्स के अंतराल जैसे व्यापक सबूत प्रदान करेगा। विस्तार बी * एक सबसे अच्छी-पहली प्रक्रिया है, जिसका अर्थ है कि पेड़ को पार करना बहुत कुशल है, विस्तार करने के लिए एक पत्ता खोजने के लिए बार-बार उतरना। यह खंड वर्णन करता है कि विस्तार के लिए नोड कैसे चुनें। (नोटः वृक्ष स्मृति-निवासी है या नहीं, यह समग्र कार्यान्वयन दक्षता का एक कार्य है, जिसमें यह भी शामिल है कि इसे वास्तविक या आभासी स्मृति के माध्यम से कैसे मैप और/या प्रबंधित किया जा सकता है।) वृक्ष की जड़ में, एल्गोरिथ्म दो रणनीतियों में से एक को लागू करता है, जिसे प्रूफ-बेस्ट और डिसप्रूव-रेस्ट कहा जाता है। साबित-सर्वश्रेष्ठ रणनीति में, एल्गोरिथ्म उच्चतम ऊपरी सीमा से जुड़े नोड का चयन करता है। उम्मीद है कि उस नोड का विस्तार करने से इसकी निचली सीमा किसी भी अन्य नोड की ऊपरी सीमा की तुलना में अधिक बढ़ जाएगी। अस्वीकृत-विश्राम रणनीति उस मूल के बच्चे का चयन करती है जिसकी दूसरी सबसे बड़ी ऊपरी सीमा होती है। उम्मीद है कि उस नोड का विस्तार करके आप ऊपरी सीमा को सबसे अच्छे बच्चे की निचली सीमा से कम करने में सक्षम हो सकते हैं। रणनीति चयन ध्यान दें कि अस्वीकृत-विश्राम रणनीति को तब तक लागू करना व्यर्थ है जब तक कि चाइल्ड नोड की निचली सीमा जिसमें उच्चतम ऊपरी सीमा होती है, सभी निचली सीमाओं में सबसे अधिक नहीं होती है। मूल एल्गोरिथ्म विवरण ने किस रणनीति का चयन करना है, इस पर कोई और मार्गदर्शन नहीं दिया। कई उचित विकल्प हैं, जैसे कि उस विकल्प का विस्तार करना जिसमें छोटा पेड़ हो। गैर-जड़ नोड्स पर रणनीति चयन एक बार जब जड़ के बच्चे का चयन किया जाता है (प्रूफ-बेस्ट या डिसप्रूव-रेस्ट का उपयोग करके) तो एल्गोरिथ्म बार-बार उस बच्चे का चयन करके लीफ नोड पर उतरता है जिसकी ऊपरी सीमा सबसे अधिक होती है। जब एक लीफ नोड तक पहुँच जाता है, तो एल्गोरिथ्म सभी उत्तराधिकारी नोड्स उत्पन्न करता है और मूल्यांकन कार्य का उपयोग करके उन्हें अंतराल प्रदान करता है। फिर सभी नोड्स के अंतराल का बैकअप ऑपरेशन का उपयोग करके बैकअप लेना पड़ता है। जब स्थानांतरण संभव हो, तो बैक-अप ऑपरेशन को उन नोड्स के मूल्यों को बदलने की आवश्यकता हो सकती है जो चयन पथ पर नहीं थे। इस मामले में, एल्गोरिथ्म को बच्चों से सभी माता-पिता को संकेतों की आवश्यकता होती है ताकि परिवर्तनों का प्रचार किया जा सके। ध्यान दें कि प्रसार तब बंद हो सकता है जब एक बैकअप ऑपरेशन एक नोड से जुड़े अंतराल को नहीं बदलता है। दृढ़ता यदि अंतराल गलत हैं (इस अर्थ में कि नोड का खेल-सैद्धांतिक मूल्य अंतराल के भीतर निहित नहीं है), तो बी * सही मार्ग की पहचान करने में सक्षम नहीं हो सकता है। हालाँकि, एल्गोरिथ्म व्यवहार में त्रुटियों के लिए काफी मजबूत है। मावेन (स्क्रैबल) कार्यक्रम में एक नवाचार है जो मूल्यांकन त्रुटियों के संभव होने पर बी * की मजबूती में सुधार करता है। यदि अलग होने के कारण कोई खोज समाप्त हो जाती है तो मावेन सभी मूल्यांकन अंतरालों को थोड़ी मात्रा में बढ़ाने के बाद खोज को फिर से शुरू करता है। यह नीति उत्तरोत्तर वृक्ष को चौड़ा करती है, अंततः सभी त्रुटियों को मिटा देती है। दो-खिलाड़ी खेलों का विस्तार बी * एल्गोरिथ्म दो-खिलाड़ी निर्धारक शून्य-राशि वाले खेलों पर लागू होता है। वास्तव में, एकमात्र परिवर्तन उस नोड में चलने वाले पक्ष के संबंध में "सर्वश्रेष्ठ" की व्याख्या करना है। इसलिए आप अधिकतम लेंगे यदि आपका पक्ष आगे बढ़ रहा है, और न्यूनतम यदि प्रतिद्वंद्वी आगे बढ़ रहा है। समान रूप से, आप आगे बढ़ने के लिए पक्ष के दृष्टिकोण से सभी अंतरालों का प्रतिनिधित्व कर सकते हैं, और फिर बैक-अप ऑपरेशन के दौरान मूल्यों को नकार सकते हैं। एंड्रयू पाले ने शतरंज के लिए बी * आवेदन किया। अंतिम बिंदु मूल्यांकन शून्य-चाल खोजों को निष्पादित करके किए गए थे। एक ही हार्डवेयर पर चलने वाले अल्फा-बीटा छंटाई खोज इंजनों की तुलना में इस प्रणाली ने कितना अच्छा प्रदर्शन किया, इसकी कोई रिपोर्ट नहीं है। मावेन (स्क्रैबल) कार्यक्रम ने अंतिम खेल के लिए बी * खोज को लागू किया। एक हेयुरिस्टिक योजना प्रणाली का उपयोग करके अंतिम बिंदु मूल्यांकन सौंपे गए थे। बी * खोज एल्गोरिदम का उपयोग संयोजन खेलों के एक समूह के योग खेल में इष्टतम रणनीति की गणना करने के लिए किया गया है। यह भी देखें शाखा और बाध्य संदर्भ ग्राफ एल्गोरिदम रूटिंग एल्गोरिदम खोज एल्गोरिदम संयोजन अनुकूलन खेल कृत्रिम बुद्धिमत्ता