एक भूलभुलैया को हल करने और हल करने के लिए एक ढेर का उपयोग करना - जावा

Question

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

सामान्य विचार का सरलतम एल्गोरिथ्म मैं वास्तविक कार्यक्रम में खुद को लागू करना चाहते हैं मेरा मानना ​​है कि किया जाना चाहिए:

1) Move forward 
2) Are you at a wall? 
2a) If yes, turn left 
3) Are you at the finish? 
3a) If no, go to 1 
3b) If yes, solved 

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

O O O O O X O 
X X O X O O X 
O X O O X X X 
X X X O O X O 
X X X X O O X 
O O O O O O O 
X X O X X X O 

Answer 1

:

यह वही है एक नमूना भूलभुलैया एक्स दीवारों के रूप में है, और भूलभुलैया में हे के रूप में खुली जगह के साथ की तरह है, जहां आप नीचे दाईं ओर शुरू देखने के लिए और शीर्ष बाईं ओर पार करने की कोशिश करेगा, है

आप एक

Stack<Point> points = new Stack<>(); 

// add a point 
Point p = new Point(x, y); 
if (points.contains(p)) 
    // been here before, in circles. 
else 
    points.add(p); 

Answer 2

का उपयोग आप सुनिश्चित करें कि आपके एल्गोरिथ्म किसी भी उलझन को हल किया जा रहे हैं सकता है? मुझे लगता है कि (जहां एस शुरू है और एफ खत्म है) यह इस सरल नकली में अटक जाते हैं:

xxxxxxxxxx 
Sooooooxxx 
xxxxxxoxxx 
xxxxxxFxxx 

आपका एल्गोरिथ्म जब तक यह गिरावट का सामना करना पड़ा पहले नीचे हॉल में आगे बढ़ना होगा, बाएं मुड़ें, का सामना करना पड़ "उत्तर" दीवार, फिर से बाएं मुड़ें, और पहले हॉलवे पर वापस चले जाओ, जहां यह दो बार फिर से चालू हो जाएगा और इस समस्या को दोहराना जारी रखेगा।

दाएं हाथ के नियम एल्गोरिदम (wikipedia page, साथ ही साथ अधिक भूलभुलैया के लिए अन्य अनुभाग देखें) लूप के बिना किसी भी भूलभुलैया को हल करना चाहिए, और जावा में लागू करने के लिए काफी आसान होना चाहिए।

Answer 3

एल्गोरिथ्म आप backtracking इस्तेमाल कर सकते हैं के लिए (संपादित हालांकि यह काफी अपने सामान्य विचार से मेल नहीं खाता।) तुम बस महसूस करने के लिए अपने आंदोलनों "धक्का दे दिया" कर रहे हैं एक आभासी ढेर में है, और वे unpushed होना चाहिए (और इसलिए पूर्ववत किया गया है।) यदि आपको "रोबोट" वास्तव में चलती वस्तु है तो आपको खुद को ढेर करना पड़ सकता है, लेकिन अगर आप भूलभुलैया को हल करना चाहते हैं तो आप कॉल स्टैक पर भरोसा कर सकते हैं।

Answer 4

एल्गोरिदम भाग के लिए, स्टैक के माध्यम से पहली बार गहराई को प्राथमिकता दी जाती है। की तर्ज पर कुछ:

currentSpot = (0,0) // The starting point // 

while(! currentSpot.isExit()) { 

    if (! currentSpot.left().isWall()) stack.push(currentSpot.left()); 
    if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward()); 
    if (! currentSpot.right().isWall()) stack.push(currentSpot.right()); 

    currentSpot = stack.pop(); // Get the next location // 
} 

आप अपनी बात वर्ग (पिछड़े को छोड़कर) प्रत्येक दिए गए दिशा में अगले अंक वापस जाने के लिए, साथ ही पता लगाने के लिए जब आप भूलभुलैया के किनारों पर होगी चाहता हूँ। आप शायद एक भूलभुलैया वर्ग चाहते हैं जिसमें सभी बिंदुएं हों, प्रिंटिंग करता है, एक्स/ओ इत्यादि स्टोर करता है। तो, आप संभवतः प्रारंभिक वर्तमानस्पॉट = (0,0) को वर्तमानस्पॉट = Maze.getStartingSpot() के साथ बदल सकते हैं। ;

Answer 5

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

Answer 6

उपयोग दीवार अनुयायी एल्गोरिथ्म: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Answer 7

हम इस समस्या को एक बार घेरने की कोशिश की है जब मैं स्कूल में था और हम एक समाधान सही/बाएँ हाथ के नियम के लिए इसी तरह इस्तेमाल किया। मेरा मानना ​​है कि हमने लिंक्ड सूचियों के बारे में सीखते समय ऐसा किया था। संक्षेप में, एल्गोरिथ्म इस तरह था:

1. जाओ छोड़ दिया है। यदि संभव हो, दोहराना।
2. यदि नहीं, तो सीधे जाएं। यदि संभव हो, तो चरण 1 पर वापस जाएं।
3. यदि नहीं, तो सही हो जाएं। यदि संभव हो, तो चरण 1 पर वापस जाएं।

प्रत्येक चरण में, आप यह भी देखने के लिए जांचते हैं कि आप जिस स्थान पर खड़े हैं, वह खत्म है या नहीं। यदि आप जारी रखने में असमर्थ हैं (यानी, बाएं, सीधे, या दाएं जाने में सक्षम नहीं), तो आप उस स्थान को चिह्नित करते हैं जिसे आप 'विज़िट' के रूप में खड़े कर रहे हैं और बैक अप लेते हैं। धोये और दोहराएं।