मैनहट्टन एक स्वीकार्य ह्युरिस्टिक कैसे दूरी है?

Question

क्या यह सच नहीं है कि 1 टाइल के लिए चालों की गिनती करते समय अन्य टाइल्स उनके लक्ष्य स्थिति में जा सकते हैं? और इसलिए प्रत्येक टाइल के लिए गिनती हमें लक्ष्य स्थिति तक पहुंचने के लिए आवश्यक न्यूनतम चाल से अधिक गिनती दे सकती है?

यह प्रश्न 15-पहेली के लिए मैनहट्टन दूरी के संदर्भ में है।

हम एन पहेली के लिए एक स्वीकार्य अनुमानी के रूप में मैनहट्टन दूरी का उपयोग कर सकते हैं:

यहां विभिन्न शब्दों में प्रश्न है। ए * खोज को लागू करने के लिए हमें एक स्वीकार्य ह्युरिस्टिक की आवश्यकता है। मैनहट्टन हेरिस्टिक एक उम्मीदवार है? यदि हां, तो आप उपर्युक्त तर्क (प्रश्न में पहले 3 वाक्यों) का सामना कैसे करते हैं?

परिभाषाएं: A* एक प्रकार का खोज एल्गोरिदम है। यह लक्ष्य के अनुमानित दूरी को निर्धारित करने के लिए एक ह्युरिस्टिक फ़ंक्शन का उपयोग करता है। जब तक यह ह्युरिस्टिक फ़ंक्शन कभी भी लक्ष्य की दूरी को अधिक महत्व नहीं देता है, तब तक एल्गोरिदम को सबसे छोटा रास्ता मिलेगा, शायद चौड़ाई की तुलना में तेज़ी से पहली खोज होगी। एक उदारवादी जो उस शर्त को संतुष्ट करता है स्वीकार्य है।

Answer 1

स्वीकार्य हेरिस्टिक को इस समस्या को हल करने के लिए चालों की संख्या को अधिक महत्व नहीं देना चाहिए। चूंकि आप केवल एक ही समय में ब्लॉक 1 को स्थानांतरित कर सकते हैं और केवल 4 दिशाओं में से एक में, प्रत्येक ब्लॉक के लिए इष्टतम परिदृश्य यह है कि इसमें अपने लक्ष्य स्थिति के लिए एक स्पष्ट, अनियंत्रित पथ है। यह एक एमडी है 1.

ब्लॉक की एक जोड़ी के लिए शेष राज्य उप-इष्टतम हैं, जिसका अर्थ यह है कि सही जगह पर ब्लॉक प्राप्त करने के लिए एमडी से अधिक चाल लेते हैं। इस प्रकार, उदारवादी कभी भी अनुमान नहीं लगाता है और स्वीकार्य है।

जब कोई व्यक्ति सही, औपचारिक संस्करण पोस्ट करता है तो मैं हटा दूंगा।

Answer 2

औपचारिक सबूत: एच, एच (एस *) = 0 की परिभाषा के अनुसार, यदि एस * लक्ष्य स्थिति है। विरोधाभास द्वारा प्रमाण के लिए मान लें कि कुछ शुरुआती राज्य s0 के लिए सी * < एच (एस 0)। ध्यान दें, चूंकि प्रत्येक क्रिया केवल एक टाइल ले जा सकती है, इसलिए एक क्रिया करने से अधिकतम एक से कम हो सकता है। चूंकि लक्ष्य सी * क्रियाओं में पहुंचा जा सकता है, हमारे पास एच (एस *) ≥ एच (एस 0) - सी *> 0 है, जो हमें विरोधाभास में लाता है क्योंकि एच (एस *) शून्य होना चाहिए। इसलिए, हमारे पास एच (एस 0) ≤ सी * फॉरल एस 0 होना चाहिए, और एच स्वीकार्य है। (स्रोत: कैलिफोर्निया विश्वविद्यालय, इरविन)