समस्या को हल करने के लिए ग्राफ सैद्धांतिक तरीका ग्राफ के प्रत्येक कन्फेक्शन के रूप में बोर्ड की हर कॉन्फ़िगरेशन की कल्पना करना है और फिर मैनहट्टन की दूरी पर कुछ चीजों के आधार पर छंटनी के साथ सांस की पहली खोज का उपयोग करें समाधान से प्रारंभिक विन्यास से पथ।
इस दृष्टिकोण के साथ एक समस्या यह है कि n x n
बोर्ड जहां n > 3
खेल स्थान इतना बड़ा हो जाता है कि यह स्पष्ट नहीं है कि आप विज़िट किए गए शीर्षकों को कुशलतापूर्वक कैसे चिह्नित कर सकते हैं। दूसरे शब्दों में यह आकलन करने का कोई स्पष्ट तरीका नहीं है कि बोर्ड की वर्तमान कॉन्फ़िगरेशन किसी ऐसे व्यक्ति के समान है जिसे पहले किसी अन्य पथ के माध्यम से खोजा गया था। एक और समस्या यह है कि ग्राफ का आकार n
(यह लगभग (n^2)!
) के साथ इतनी तेज़ी से बढ़ता है कि यह केवल ब्रू-फोर्स अटैक के लिए उपयुक्त नहीं है क्योंकि पथों की संख्या ट्रैवर्स के लिए कम्प्यूटेशनल रूप से अक्षम हो जाती है।
इयान पेबेरी A Real-Time Algorithm for the (n^2 − 1)
- Puzzle द्वारा यह पेपर एक साधारण लालची एल्गोरिदम का वर्णन करता है जो पहली पंक्ति को पूरा करके समाधान पर आता है, फिर पहला स्तंभ, फिर दूसरी पंक्ति ... यह लगभग तुरंत समाधान पर आता है, हालांकि समाधान इष्टतम से दूर है; अनिवार्य रूप से यह किसी भी कम्प्यूटेशनल मांसपेशियों का लाभ उठाए बिना किसी समस्या के कारण समस्या को हल करता है।
यह समस्या रुबिक के घन को हल करने के लिए निकटता से संबंधित है। सभी गेम का ग्राफ ब्रू फोर्स द्वारा हल करने के लिए बहुत बड़ा है, लेकिन एक साधारण सरल 7 कदम विधि है जिसका उपयोग किसी भी घनत्व को मानव शरीर द्वारा लगभग 1 ~ 2 मिनट में हल करने के लिए किया जा सकता है। यह पथ निश्चित रूप से गैर-इष्टतम है। उन पैटर्न को पहचानना सीखकर जो चाल के अनुक्रमों को परिभाषित करते हैं, गति को 17 seconds पर लाया जा सकता है। हालांकि, जिरी द्वारा यह उपलब्धि कुछ हद तक अतिमानवी है!
विधि पैराबेरी एक समय में केवल एक टाइल चालित करती है; एक कल्पना करता है कि जिरी की निपुणता को नियोजित करके और एक समय में कई टाइल्स को स्थानांतरित करके एल्गोरिदम को बेहतर बनाया जा सकता है। ऐसा नहीं होगा, जैसा कि पार्बेरी साबित होता है, n^3
से पथ की लंबाई को कम करें, लेकिन यह प्रमुख अवधि के गुणांक को कम करेगा।
यह compsci होमवर्क की तरह गंध करता है! –
इसकी काफी कॉम्पसी होमवर्क समस्या – monksy