3x3 त्रि-आयामी बॉक्स पहेली को हल करने के लिए ए * खोज एल्गोरिदम का उपयोग करना?

Question

मैं अपने होमवर्क में 3x3 त्रि-आयामी बॉक्स पहेली समस्या पर काम कर रहा हूं। मैं सी

साथ कोड होगा

26 बॉक्स हैं और पहली बार में, पहली जगह खाली है। बक्से स्लाइड करके मुझे उन्हें सही क्रम में व्यवस्थित करना होगा। लाल संख्याएं सही क्रम दिखाती हैं और आखिरी जगह 27 वां स्थान खाली होना चाहिए। मैं नहीं चाहता कि आप मुझे कोड दें; मैंने फ़ोरम में खोज की और ऐसा लगता है कि मुझे A* search algorithm का उपयोग करना चाहिए, लेकिन कैसे?

क्या आप मुझे इस समस्या पर ए * एल्गोरिदम का उपयोग करने के बारे में सुझाव दे सकते हैं? मुझे किस प्रकार की डेटा संरचना का उपयोग करना चाहिए?

Answer 1

आप जानते हैं कि ग्राफ कैसे काम करते हैं और कैसे ए * उन पर सबसे कम पथ पाता है, है ना?

मूल विचार यह है कि पहेली के प्रत्येक कॉन्फ़िगरेशन को ग्राफ में वर्टेक्स माना जा सकता है और किनारों को चाल का प्रतिनिधित्व करते हैं (चालन से पहले और बाद में कॉन्फ़िगरेशन को जोड़कर)।

किसी मूल कॉन्फ़िगरेशन से वांछित व्यक्ति की ओर जाने वाली चालों का एक सेट ढूंढना पथ खोजने की समस्या के रूप में देखा जा सकता है।

Answer 2

एक राज्यों ग्राफ के रूप में आपकी समस्या को परिभाषित करें:
G=(V,E) जहां V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [प्रत्येक संख्या 3 डी बोर्ड पर एक 'वर्ग' का प्रतिनिधित्व कर रहा है]।
वी में प्रत्येक वी के लिए::
और E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} परिभाषित E के लिए एक वैकल्पिक परिभाषा [समान] समारोह successors(v) का उपयोग करना है successors(v)={all possible boards you can get, with 1 step from v}

तुम भी एक admissible heuristic function, इस समस्या हो सकती है के लिए एक बहुत अच्छी एक की आवश्यकता होगी: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) मूल रूप से, यह अपने लक्ष्य से प्रत्येक संख्या के लिए manhattan distances का सारांश है।

अब, एक बार हमें यह डेटा मिलने के बाद, परिभाषित हेरिस्टिक के साथ परिभाषित ग्राफ जी पर हम ए * चलाना शुरू कर सकते हैं। और चूंकि हमारे ह्युरिस्टिक फ़ंक्शन स्वीकार्य है [खुद को समझें क्यों!], यह गारंटी है कि admissibility and optimality of A* के कारण समाधान ए * पाता इष्टतम होगा।
वास्तविक पथ ढूँढना: ए * समाप्त हो जाएगा जब आप लक्ष्य स्थिति विकसित करेंगे। [x_i=i हमारे द्वारा पहले इस्तेमाल किए गए शब्दों में]। प्रत्येक नोड में parent फ़ील्ड का उपयोग करके, आपको लक्ष्य से स्रोत तक वापस कदम से अपना रास्ता मिल जाएगा।