मैंने कुछ बड़े (उच्च आयाम) टिक-टैक-टो खेल के लिए कुछ हेरिस्टिक्स के बारे में सोचा है। मैं कैसे जांचूं कि उनमें से कौन सा वास्तव में संगत है?गेम प्रोग्रामिंग में, मैं कैसे परीक्षण कर सकता हूं कि एक हेरिस्टिक इस्तेमाल किया गया है या नहीं?
स्थिरता क्या मतलब है?
संपादित किया गया: यह उत्तर स्वीकार्यता और स्थिरता को उलझन में डाल दिया। मैंने इसे स्वीकार्यता के संदर्भ में सही किया है, लेकिन मूल प्रश्न स्थिरता के बारे में था, और यह उत्तर पूरी तरह से प्रश्न का उत्तर नहीं देता है।
आप सभी अलग-अलग मामलों को अलग करके विश्लेषणात्मक रूप से ऐसा कर सकते हैं और साबित कर सकते हैं कि आपका उत्तराधिकारी वास्तव में स्वीकार्य है।
सूचित खोज के लिए, के लिए अनुमान का एक खोज समस्या से स्वीकार्य है (जैसे कि, एक खेल में सबसे अच्छा कदम के लिए खोज) यदि और केवल यदि यह underestimates एक उपयुक्त राज्य के लिए 'दूरी'।
उदाहरण: शहरों के बीच राजमार्गों के नेटवर्क के माध्यम से एक लक्षित शहर के सबसे छोटे मार्ग की खोज करें। यहां, कोई यूकाइडियन दूरी को एक ह्युरिस्टिक के रूप में उपयोग कर सकता है: लक्ष्य की सीधी रेखा की लंबाई हमेशा संभव या कम से कम लंबी संभव तरीके से लंबी होती है।
A* जैसे एल्गोरिदम द्वारा स्वीकार्यता की आवश्यकता है, जो तब आपको इष्टतम होने के लिए गारंटी देता है (यानी यदि कोई मौजूद है तो उन्हें लक्ष्य स्थिति में सर्वश्रेष्ठ 'मार्ग' मिलेगा)।
मैं AI textbook में विषय को देखने की अनुशंसा करता हूं।
स्वीकार्य और सुसंगत ह्युरिस्टिक्स के बीच भी एक अंतर है, हालांकि सभी लगातार हेरिस्टिक्स स्वीकार्य हैं। स्वीकार्य अर्थ यह है कि हेरिस्टिक कुल पथ लागत को कम करके आंका जाता है और यह एक स्थिरता के बाद चरण लागत से अधिक नहीं होने पर हेरिस्टिक कम हो जाता है। –
हेरिस्टिक्स किसी दिए गए राज्य के लिए किसी प्रकार का मूल्य मूल्य उत्पन्न करता है। इस संदर्भ में संगति का मतलब है कि राज्य के लिए अनुमान और अगले राज्य में जाने की लागत उस नए राज्य के अनुमान से कम या बराबर है। यदि यह सत्य नहीं था तो यह इंगित करेगा कि - यदि ह्युरिस्टिक सटीक था - कि एक राज्य से अगले राज्य में संक्रमण को नकारात्मक लागत लग सकती है, जो आम तौर पर असंभव या गलत है।
यह पथदर्शी होने पर साबित करने के लिए सहज है, क्योंकि आप कुछ समय लेने के लिए पथ के साथ हर कदम की अपेक्षा करते हैं, इसलिए चरण 1 पर अनुमान किसी भी चरण 2 के अनुमान से कम होना चाहिए। यह शायद थोड़ा और अधिक है टिक-टैक-टो के लिए जटिल है क्योंकि आपको शायद मनमाने ढंग से निर्णय लेना होगा कि आपके सिस्टम में 'लागत' क्या है। यदि आपका उत्साही चलने के परिणामस्वरूप दोनों ऊपर या नीचे जा सकते हैं - उदाहरण के लिए। क्योंकि आप नकारात्मक संख्याओं के साथ सकारात्मक संख्याओं और बुरी चालों के साथ अच्छी चाल को एन्कोड करते हैं - तो आपका उत्तराधिकारी सुसंगत नहीं हो सकता है।
हालांकि, लगातार हेरिस्टिक की कमी हमेशा एक समस्या नहीं है। आपको बिना किसी इष्टतम समाधान तक पहुंचने की गारंटी नहीं दी जा सकती है, लेकिन यह अभी भी ब्रूट फोर्स स्टेट सर्च की तुलना में खोज को तेज कर सकता है।
यह एक असली सवाल है। –
दो लोगों ने इसे 'वास्तविक प्रश्न नहीं' के रूप में बंद करने के लिए ध्वजांकित किया है। मैं भी उनके साथ असहमत हूं। – Kylotan