मुझे एआईएमए (Artificial Intelligence: A Modern Approach) में एल्गोरिदम विवरण मिल गया है बिल्कुल सही नहीं है। 'जरूरी' मतलब क्या है? स्मृति सीमा क्या है? कतार आकार या संसाधित नोड्स? क्या होगा यदि वर्तमान नोड में कोई बच्चा नहीं है?किसी ने भी एसएमए * खोज एल्गोरिदम लागू किया है?
मुझे आश्चर्य है कि यह एल्गोरिदम स्वयं सही है या नहीं। क्योंकि मैंने इंटरनेट की खोज की है और किसी ने अभी तक इसे लागू नहीं किया है।
धन्यवाद।
मेरा मानना है कि this PDF एआईएमए से एसएमए * अनुभाग है, जिनके पास पुस्तक नहीं है।
मैं पहली बार स्यूडोकोड ध्यान दें विकिपीडिया से लाइन में एक नहीं बल्कि स्पष्ट त्रुटि है: (कैसे एक माता पिता के लिए अपने स्वयं के उत्तराधिकारी हो सकता है)
parent.successors.remove(parent);
यह होना चाहिए
parent.successors.remove(badNode);
'आवश्यक' का क्या अर्थ है?
यदि उसके माता-पिता पहले से ही कतार में नहीं हैं, तो हमें इसे कतार में जोड़ना होगा। अन्यथा, हम फिर से इस नोड को खोजना समाप्त कर देंगे।
मेमोरी सीमा क्या है? कतार आकार या संसाधित नोड्स?
कतार सभी उपलब्ध स्मृति को उठाएगी। संसाधित नोड्स के लिए कोई कतार नहीं है। यही कारण है कि एसएमए * नोड्स को फिर से चला सकता है और संभावित रूप से फंस जाता है।
क्या होगा यदि वर्तमान नोड में कोई बच्चा नहीं है?
यदि किसी नोड में कोई बच्चा नहीं है, तो यह एक पत्ता नोड है। और यदि यह एक पत्ता नोड है, तो यह एक टर्मिनल नोड है। उस स्थिति में, यदि यह लक्ष्य नोड नहीं है, तो हम अपनी एफ-लागत को अनंत तक सेट करते हैं, और उस जानकारी को अपने माता-पिता को प्रचारित करते हैं।
मैं सी # में इसके साथ ग्राफ खोज लागू करने के लिए, the PDF का उपयोग कर प्रबंधित किया है।
मैंने 3 सूचियों का उपयोग किया है - फ्रंटियर (खुली सूची), पत्ता सूची और "पेड़ शाखा" सूची।
फ्रंटियर कतार, पीडीएफ में उल्लेख किया है, यह एक आम प्राथमिकता कतार सबसे अच्छा से सबसे खराब करने के लिए हल कर सकता है।
पत्ता सूची केवल सबसे खराब से हल कर के लिए सबसे अच्छा है, हम इसे की आवश्यकता होगी जब हम तय करेंगे कि क्या पत्ती भूल जाते हैं पत्ते, रहता है। एसएमए केवल शाखाओं को भूल जाता है, न कि पूरी शाखाएं।
पेड़ की टहनी सूची पूरी तरह से विस्तृत नोड्स, जिसका बच्चों सभी स्मृति में हैं रहता है। राज्य चौराहे का परीक्षण करने के लिए हमें इसकी आवश्यकता होगी।
मैंने फ्रंटियर और लीफ सूची के लिए फास्ट बाइनरी ढेर और पेड़ शाखा सूची के लिए हैश टेबल का उपयोग किया है।स्थिति के साथ
उत्तराधिकारियों इटरेटर (स्थिति उत्तराधिकारियों की सूची में उनका कहना है के लिए आवश्यक है):
नोड्स निम्न अतिरिक्त जानकारी रखना चाहिए। अगर हम जाते हैं तो हम पूरी तरह से हमारे उत्तराधिकारी गणना को शून्य पर रीसेट नहीं करना चाहिए, क्योंकि यह संभव है, क्योंकि हम जो नोड हमने अभी जोड़ा है उसे भूल जाते हैं। मैं "समाप्त" ध्वज के लिए स्थिति और बूल के लिए आईएन्यूमेरेटर, int का उपयोग करता हूं।
उत्तराधिकारी सूची। हमें अनिवार्य रूप से एफ-लागत ऊपर प्रचार के लिए इसकी आवश्यकता है। इसके अलावा मैं सरल उत्तराधिकारी राज्य सूची भी रखता हूं - जैसे [अवरुद्ध, भूल गया, मौजूद]। भूल गए और अवरुद्ध नोड्स का ट्रैक रखने के लिए इसकी आवश्यकता है। (अवरुद्ध - ग्राफ में - कुछ नोड है, जो तेजी से विस्तार से)
दो एफ के, पीडीएफ, हमारे वर्तमान एफ में उल्लेख किया है, और सबसे अच्छा भूल उत्तराधिकारी एफ
नोड गहराई
दोनों फ्रंटियर और लीफ सूची में नोड्स को सॉर्ट करना इस प्रकार किया जाना चाहिए: "यदि हमने गणित ध्वज" समाप्त "किया है, तो सबसे अच्छा भूल गए उत्तराधिकारी एफ चुनें, अन्यथा मौजूदा एफ चुनें, यदि बराबर है, तो गहन चुनें"। लीफ सूची को उसी स्थिति का उपयोग करके रिवर्स ऑर्डर में क्रमबद्ध किया जाता है।
बेसिक एल्गोरिथ्म रूपरेखा (पीडीएफ़ के समान) इस तरह है:
हम सीमा से सबसे अच्छा नोड लेने, है अगर यह "समाप्त" झंडा - हम जानते हैं कि हम याद किया जाएगा, इटरेटर रीसेट, और हमें इस मामले में सबसे अच्छे उत्तराधिकारी एफ को रीसेट करना होगा (जटिल कारणों से)।
यदि हमारे पास पहले से ही सूची में यह उत्तराधिकारी नहीं है (हो सकता है, जब हम याद कर रहे हों) - हम इसे उत्पन्न करते हैं और पीडीएफ में वर्णित एफ को सेट करते हैं।
फिर सबसे जटिल चीज का पालन करता है - हम परीक्षण करते हैं कि एक ही राज्य के साथ नोड सीमा या पेड़ शाखा सूची में मौजूद है या नहीं। अगर ऐसा होता है - मैं वर्णन करूंगा कि बाद में क्या करना है। यदि नहीं, तो हम केवल बच्चे को सीमा में जोड़ें (और पत्ती सूची से माता-पिता को हटा दें)।
सभी मामलों में जब उत्तराधिकारी की गणना समाप्त होती है - हम एफ-लागत के तथाकथित बैकअप करते हैं, और यदि हमारे पास कोई भूल गए नोड्स (और कुछ उत्तराधिकारी हैं) नहीं हैं, तो हम सीमा से वर्तमान नोड को हटाते हैं और इसे पेड़ शाखा सूची में जोड़ें।
कैसे भूल जाते हैं: हम पत्ती सूची (सबसे खराब पत्ती) से पहले पत्ती लेने, सीमा से हटाने, माता पिता के उत्तराधिकारियों सूची से निकालने, अद्यतन (कमी) माता-पिता की सबसे अच्छी भूल उत्तराधिकारी के एफ, यदि आवश्यक हो तो, और यदि माता-पिता सीमा पर नहीं है - हम इसे पेड़ की शाखा सूची से हटा देते हैं और इसे सीमा में जोड़ते हैं और इसे पत्ती सूची में भी जोड़ते हैं, अगर यह अब एक पत्ता है (अब उत्तराधिकारी नहीं हैं)।
अगर हम उत्तराधिकारी उत्पन्न करते हैं, तो क्या करना है, जो पहले से ही सीमा या पेड़ शाखा सूची में है। सबसे पहले, हमें इसकी बेहतर जांच करने की आवश्यकता होगी - हम दो नोड्स के पथकोस्ट + एच ("मूल" एफ) की तुलना करते हैं। ध्यान दें, कि हम बैक-अप एफ की तुलना नहीं कर सकते - यह काम नहीं करेगा। यदि यह बेहतर नहीं है - हम केवल उत्तराधिकारी राज्य को अवरुद्ध करने के लिए सेट करते हैं। यदि ऐसा है - तो मामला हो सकता है, कि बदतर नोड एक विशाल उपखंड की जड़ है (फिर से समझाने के लिए बहुत जटिल)। इस मामले में हम पूरी तरह से उपट्री काटते हैं और एसएमए एक बार में नोड्स का गुच्छा भूल जाता है। बेहतर नोड के साथ बदतर नोड को बदलने के बाद, हम इसके माता-पिता उत्तराधिकारी सूची से, फ्रंटियर, लीफ लिस्ट, या यहां तक कि वृक्ष शाखा सूची से भी खराब नोड हटाते हैं (यह भी वहां हो सकता है!), इसके माता-पिता के लिए अवरुद्ध करने के लिए उत्तराधिकारी राज्य सेट करें और यह जांचना न भूलें कि क्या बदतर नोड के माता-पिता के पास अब सभी नोड्स अवरुद्ध हैं - हमें इसे एफ को अनंतता में सेट करने की आवश्यकता होगी, क्योंकि यह टर्मिनल नोड बन गया है।
शायद मुझे सबसे सरल कार्यान्वयन नहीं मिला है, लेकिन यह केवल यही है, जो मेरे लिए काम करता है। मैंने परीक्षणों के लिए 8-पहेली का उपयोग किया है - कम से कम (एन + 1) -मेमरी (नोड शुरू करने की गिनती) के साथ एन-चरणों को हल करना, और पारंपरिक ए-स्टार के साथ समाधान इष्टतमता की जांच करना। मैंने 20-30 घंटों की तरह सभी विवरणों को समझने की कोशिश की है - मुख्य समस्या विफल परीक्षण मामलों की जटिलता में थी - मुझे "बेहतर नोड के साथ प्रतिस्थापन" तर्क बग केवल 20+ चरणों पर मिला है हजारों यादृच्छिक बीज का व्यापक परीक्षण। प्राथमिकता कतारों के लिए भी देखें - मुझे आइटम को इतने सारे मामलों में पुन: सम्मिलित करना पड़ा, क्योंकि एफ में कोई भी बदलाव, सबसे अच्छा भूल गया एफ, या "समाप्त" ध्वज - सॉर्ट ऑर्डर बदलता है। मैं हर डेक्यू पर अपनी बाइनरी ढेर स्थिरता की जांच समाप्त हो गया। और अंतहीन साइकलिंग की बग को समझने के लिए सबसे जटिल से छुटकारा पाने का मुख्य विचार यह जांचना है कि आप सभी मामलों में एफ को कम नहीं करते हैं। इस तरह एफ की वृद्धि जारी रहेगी।
मैं कुछ हफ्तों में कार्य कार्यान्वयन स्रोत साझा करने जा रहा हूं।
क्या यह किसी प्रकार का * है? –
क्या आपने एमा-टॉक ग्रुप की कोशिश की है? http://tech.groups.yahoo.com/group/aima-talk/ –
आप क्यों मान रहे हैं कि सभी के पास यह पुस्तक है और आप जो कुछ भी बोल रहे हैं उसे पढ़ें। और यह प्रोग्रामिंग कैसे संबंधित है यदि कुछ पुस्तक में कुछ विवरण सही है या नहीं – jitter