एक भूलभुलैया से चूहा प्राप्त कर रहा है

Question

भूलभुलैया में किसी अज्ञात स्थिति पर एक चूहे को एक भूलभुलैया में रखा गया है।

हम सभी जा सकते हैं ऊपर, नीचे, दाएं या बाएं दिशाओं में।

• tryMove (< दिशा >) जो झूठे रिटर्न अगर वहाँ एक दीवार और सच अगर हम ले जा सकते हैं है: और हम दो तरीकों की है।
• बूल हैडडर(): अगर सीढ़ी से बचने के लिए सही होता है तो यह सच हो जाता है।

हमें एक फ़ंक्शन एक्सप्लोर लिखना होगा जो अगर कोई रास्ता नहीं है तो हमें रास्ता या झूठा लगता है।

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

Answer 1

दोनों चौड़ाई-पहले और गहराई की पहली खोज में स्मृति की आवश्यकता होती है और एक बेवकूफ एल्गोरिदम अनिश्चित काल तक लूप कर सकता है। एक चूहे में केवल ओ (1) स्मृति है।

यादृच्छिक रूप से एक दिशा लेने के लिए आप कहां गए हैं, इसे याद किए बिना इसे हल करने का एक तरीका है। हल समय बहुत लंबा होगा, लेकिन अंत में यह प्रत्येक पहुंच योग्य वर्ग तक पहुंच जाना चाहिए। यह 2D random पैदल से संबंधित है।

आश्चर्यजनक रूप से, यह साबित हो चुका है कि एक दो आयामी जाली पर, एक यादृच्छिक की पैदल दूरी पर (प्रारंभिक बिंदु सहित) किसी भी बिंदु तक पहुंच गया चरणों की संख्या अनंत दृष्टिकोण के रूप में की एकता आशंका होती है।

Answer 2

आपको बीएफएस एल्गोरिदम चलाना चाहिए। एकमात्र समस्या मैं देखता हूं कि ग्राफ़ को कैसे परिभाषित किया जाए। इसे von Neumann neighborhood के साथ परिभाषित किया जा सकता है। नोड को एक्स, वाई जोड़ी के रूप में परिभाषित किया गया है।

BFS 
while (!Q.empty()){ 
    v = Q.top() 
    neighbours = get_adj_list(v) 
    foreach (w in neighbours){ 
     if (isWall(w) || isOutsideMaze(w)) skip 
     if (isTerminal(w)) printPathAndExit 
     if (dist[v] + 1 < dist[w]) 
      dist[w] = dist[v] + 1 
      Q.push(w) 
    } 
} 

GEN_NEIGHBOURS 
dx = {-1,1} 
dy = {-1,1} 

get_adj_list(v) 
    adj_list = [] 
    for (i in dx) 
     for (j in dy) 
      adj_list << node(v.x-i,v.y-j) 
    return adj_list 

संपादित: छद्म कोड की तरह दिखना चाहिए अब मैं स्मृति सीमा पढ़ा हे है (1)। तो मुझे लगता है कि आपको हमेशा सही करने के लिए पुरानी विधि का पालन करना चाहिए और अंततः आप भूलभुलैया से बाहर निकल जाएंगे या स्थिति शुरू करने के लिए वापस आ जाएंगे।

EDIT2: मकई भूलभुलैया सुझावों से:

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

Answer 3

यह एक क्लासिक समस्या है जिसे अक्सर होमवर्क असाइनमेंट के रूप में उपयोग किया जाता है।

इस प्रयास करें:

1. आप बता सकते हैं कि आप जिस तरह से बाहर अभी कर रहे हैं?
2. एक बार आपके पास यह हो जाने के बाद, क्या आप यह पता लगाने के लिए क्या करना चाहते हैं कि आप रास्ते के एक कदम के भीतर हैं या नहीं?
3. अगर आप रास्ते के 2 कदमों के भीतर हैं तो कैसे?

...

Mark notes रूप में, मैं आप का नेतृत्व करने के कोशिश कर रहा हूँ एल्गोरिथ्म का सबसे सरल संस्करण एक पाश में लॉक हो सकता है। आप इस समस्या को कैसे हल कर सकते हैं?

Answer 4

अगर मुझे सही याद है, तो मुझे बहुत समय पहले इस तरह की एक पुनरावर्ती होमवर्क असाइनमेंट थी, हालांकि यह ओ (1) स्मृति तक ही सीमित नहीं थी। हम सिर्फ 'मानचित्र' नहीं बना सकते थे जहां हम गए हैं और रिकर्सन का उपयोग करना था ... मुझे लगता है कि यह ओ (एन) मेमोरी का उपयोग करेगा, जहां सी शुरुआत से सीढ़ी की सबसे छोटी दूरी है।

while(1) 
    { 
    if(search(MOVE_LEFT, i) || 
     search(MOVE_UP, i) || 
     search(MOVE_RIGHT, i) || 
     search(MOVE_DOWN, i)) 
     { 
     return TRUE; 
     } 
    i++; 
    } 

/* recursive function */ 
bool search(move_type move, long int length) 
{ 

doMove(move); /* actually move the rat to requested place */ 

if(hasLadder()) 
    return TRUE; 

if(0 == length) 
    return FALSE; 

switch(move) /* check each and return rat to previous place */ 
    { 
    case MOVE_LEFT: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_RIGHT); break; 
    case MOVE_UP: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     doMove(MOVE_DOWN); break; 
    case MOVE_RIGHT: 
     if(tryMove(MOVE_UP) && search(MOVE_UP, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_LEFT); break; 
    case MOVE_DOWN: 
     if(tryMove(MOVE_LEFT) && search(MOVE_LEFT, length - 1)) return TRUE; 
     if(tryMove(MOVE_RIGHT) && search(MOVE_RIGHT, length - 1)) return TRUE; 
     if(tryMove(MOVE_DOWN) && search(MOVE_RIGHT, length - 1)) return TRUE;  
     doMove(MOVE_UP); break; 
    } 

return FALSE; 

} /* search() */ 

Answer 5

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

http://en.wikipedia.org/wiki/Halting_problem

Answer 6

कोई स्मृति के साथ एकमात्र समाधान यादृच्छिक है और यह भयानक है। यदि आपको पता है कि भूलभुलैया केवल एकमात्र जुड़ा हुआ है तो आप दीवार-निम्नलिखित दृष्टिकोण का उपयोग कर सकते हैं, लेकिन अगर भूलभुलैया में लूप होता है तो वह अनंत लूप में जा सकता है।

Answer 7

एल्गोरिथ्म मूल रूप से USTCON (अनिर्दिष्ट सेंट-कनेक्टिविटी) है: एक अनिर्दिष्ट ग्राफ जी को देखते हुए निर्धारित अगर वहाँ नोड रों (चूहे के प्रारंभ स्थिति) से एक पथ नोड के लिए टी (निकास) है । यह समस्या complexity class L में है, जिसका अर्थ है कि इसे logarithmic amount of memory की आवश्यकता है। इसलिए, जब तक कि आप भूलभुलैया के आकार पर ऊपरी बाध्य न हों, या अनुमान लगाने के इच्छुक हैं, निरंतर स्थान के साथ असंभव है।

Answer 8

मजेदार है कि @ mousey चूहे के बारे में पूछेगा ... anwyay।

मैंने देखा है कि यह समस्या पहले से ही कई बार रेंग रही है।

पहली (और अनुभवहीन) समाधान लेकिन यह विशिष्ट mazes जहां चूहे अंत हलकों में चल रहा है शिल्प के लिए संभव है, बाएं (या सही) दीवार का पालन है।

वास्तव में, चाल के हर निर्धारित क्रम (जैसे 2 एल, 1 आर, 2 एल, 1 आर, ...) के लिए मैंने कोशिश की (हाई स्कूल में होने के समय में) हम एक भूलभुलैया के साथ आ सकते हैं जो सर्कल में चूहा भागो। बेशक, अधिक जटिल चक्र, भूलभुलैया अधिक जटिल।

इसलिए, यदि आप हे (1) स्मृति है, एकमात्र समाधान भूलभुलैया से बाहर निकलने के रूप में चिह्नित करें बायर्स द्वारा प्रस्तावित एक यादृच्छिक की पैदल दूरी पर हो रहा है। दुर्भाग्यवश आप साबित नहीं कर सकते कि इस तरह के एल्गोरिदम के साथ भूलभुलैया से बाहर निकलना असंभव है।

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

तुम भी एक बाढ़ भरण एल्गोरिथ्म का उपयोग कर सकते ... बेशक, यह इससे पहले कि मैं अवधि BFS के बारे में सीखा था। इसका लाभ यह है कि आपके पास समाप्ति की स्थिति है (जब कोई पता लगाने के लिए कोई मामला नहीं छोड़ा गया है)।