ए * खोज

Question

के लिए अच्छा हेरिस्टिक खोजना मैं ट्विडल नामक एक छोटे पहेली गेम के लिए इष्टतम समाधान खोजने की कोशिश कर रहा हूं (गेम के साथ एक एप्लेट here पाया जा सकता है)। गेम में 1 से 9 तक की संख्या के साथ 3x3 मैट्रिक्स है। लक्ष्य कम से कम चालों का उपयोग करके संख्याओं को सही क्रम में लाने के लिए है। प्रत्येक चाल में आप 2x2 वर्ग को या तो दक्षिणावर्त या विपरीत दिशा में घुमा सकते हैं।

आईई। आप इस राज्य

6 3 9 
8 7 5 
1 2 4 

है और आप ऊपरी बाएँ 2x2 वर्ग बारी बारी से दक्षिणावर्त आप

8 6 9 
7 3 5 
1 2 4 

मिल मैं एक एक * खोज का उपयोग कर रहा इष्टतम समाधान खोजने के लिए यदि। मेरा एफ() बस आवश्यक घूर्णन की संख्या है। मेरा हेरिस्टिक फ़ंक्शन पहले से ही इष्टतम समाधान की ओर जाता है (यदि मैं इसे संशोधित करता हूं, नोटिस को अंत में देखें) लेकिन मुझे नहीं लगता कि यह सबसे अच्छा है जिसे आप पा सकते हैं। मेरा वर्तमान ह्युरिस्टिक प्रत्येक कोने लेता है, कोने पर संख्या को देखता है और स्थिति के मैनहट्टन दूरी की गणना करता है, इस संख्या को हल राज्य में होगा (जो मुझे इस पद पर संख्या लाने के लिए आवश्यक रोटेशन की संख्या देता है) और सभी को बताता है ये मूल्य अर्थात। ऊपर दिए गए उदाहरण लेते हैं:

6 3 9 
8 7 5 
1 2 4 

और यह अंत राज्य

1 2 3 
4 5 6 
7 8 9 

तो अनुमानी निम्नलिखित

6 is currently at index 0 and should by at index 5: 3 rotations needed 
9 is currently at index 2 and should by at index 8: 2 rotations needed 
1 is currently at index 6 and should by at index 0: 2 rotations needed 
4 is currently at index 8 and should by at index 3: 3 rotations needed 

h = 3 + 2 + 2 + 3 = 10 

साथ ही, यदि ज 0 है, लेकिन राज्य नहीं पूरी तरह से करता है आदेश दिया गया, एच = 1.

लेकिन समस्या है, कि आप एक बार में 4 तत्व घुमाते हैं। तो वहां एक दुर्लभ मामले हैं जहां आप एक कदम में अनुमानित घूर्णन के दो (अयस्क अधिक) कर सकते हैं। इसका मतलब यह है कि सिद्धांतों में हेरिस्टिक समाधान की दूरी को अधिक महत्व देता है।

मेरा वर्तमान कामकाज केवल गणना से कोनों में से एक को बाहर करने के लिए है जो कम से कम मेरे परीक्षण-मामलों के लिए इस समस्या को हल करता है। मैंने वास्तव में समस्या हल करने के लिए कोई शोध नहीं किया है या यदि यह हेरिस्टिक अभी भी कुछ किनारे-मामलों में अतिवृद्धि करता है।

तो मेरा प्रश्न है: सबसे अच्छा हेरिस्टिक क्या है जिसके साथ आप आ सकते हैं?

(अस्वीकरण: यह एक विश्वविद्यालय परियोजना के लिए है, इसलिए यह होमवर्क का एक छोटा सा हिस्सा है। लेकिन अगर मैं आ सकता हूं तो मैं किसी भी संसाधन का उपयोग करने के लिए स्वतंत्र हूं, इसलिए आपसे पूछना ठीक है। मेरी मदद करने के लिए स्टैकओवरफ्लो;))

Answer 1

सरलता अक्सर सबसे प्रभावी होती है। एक एकल पूर्णांक बनाने के रूप में नौ अंकों (पंक्तियों में पहला क्रम) पर विचार करें। समाधान को सबसे छोटे संभव पूर्णांक i (g) = 123456789 द्वारा दर्शाया जाता है। इसलिए मैं निम्नलिखित ह्युरिस्टिक एच (एस) = i (ओं) - i (g) का सुझाव देता हूं। आपके उदाहरण के लिए, एच (एस) = 639875124 - 123456789।

Answer 2

सभी तत्वों को दूरी की गणना करते समय ध्यान में रखा जाना चाहिए, न केवल कोने तत्वों। कल्पना करें कि सभी कोने तत्व 1, 3, 7, 9 उनके घर पर हैं, लेकिन अन्य सभी नहीं हैं।

यह तर्क दिया जा सकता है कि अंतिम तत्व में पड़ोसियों के उन तत्वों को प्रत्येक चरण के करीब होना चाहिए, इसलिए पड़ोसी दूरी भी ह्युरिस्टिक का हिस्सा हो सकती है, लेकिन संभवतः उनके अंतिम राज्य में तत्वों की दूरी से कमजोर प्रभाव के साथ ।

Answer 3

आप सभी संख्याओं को ध्यान में रखते हुए, और 4 से विभाजित करके और अगले पूर्णांक तक गोल करके एक स्वीकार्य (यानी, अतिसंवेदनशील नहीं) प्राप्त कर सकते हैं।

हेरिस्टिक में सुधार करने के लिए, आप संख्याओं के जोड़े देख सकते हैं। यदि उदा। ऊपरी बाईं ओर संख्या 1 और 2 स्वैप हो गए हैं, आपको उन्हें ठीक करने के लिए कम से कम 3 रोटेशन की आवश्यकता है, जो अलग-अलग विचारों से 1 + 1 से बेहतर मूल्य है। अंत में, आपको अभी भी 4 से विभाजित करने की आवश्यकता है। आप मनमाने ढंग से संख्याओं को जोड़ सकते हैं, या यहां तक ​​कि सभी जोड़ों को आजमा सकते हैं और जोड़े में सर्वश्रेष्ठ विभाजन ढूंढ सकते हैं।