कैसे भूलभुलैया के इस प्रकार का सबसे छोटा रास्ता खोजने के लिए

Question

Red Dot - Represents the initial location 
Black Dot - Already occupied 
Green - Free to occupy 
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8] 

उदाहरण:

red dot अपने आप में एक समय में केवल एक कदम रख सकते हैं और हरे रंग की छह में से एक में ले जा सकते हैं सर्किल जो इससे जुड़े हुए हैं। इस प्रकार के भूलभुलैया में सबसे कम पथ की गणना करने का सबसे तेज़ तरीका क्या होगा।

Answer 1

सबसे पहले, आपको डिजस्ट्रा की आवश्यकता नहीं है, क्योंकि किनारों के सभी मूल्य समान हैं। आप एक साधारण BFS या DFS एल्गोरिदम का उपयोग कर सकते हैं। सबसे खराब मामला जटिलताएं समान हैं लेकिन मैं बीएफएस का उपयोग करूंगा क्योंकि इसमें औसत औसत जटिलता है। हालांकि, ओ (| वी | + | ई |) सबसे तेज़ है जो आप यहां प्राप्त कर सकते हैं और यह साबित हुआ है।

आपके ग्राफ का प्रतिनिधित्व कैसे किया है? सबसे अच्छा तरीका प्रत्येक Node के लिए पड़ोसियों की सूची रखना है। आपके उदाहरण से काले बिंदुओं को पड़ोसियों के रूप में नहीं माना जाता है। तो आपके उदाहरण में, प्रत्येक नोड में 0 पड़ोसियों को 0 (पूरी तरह से काले बिंदुओं द्वारा कवर किया जाएगा) होगा। फिर, आप इन सूचियों के माध्यम से किसी भी नोड बिंदु से कहीं भी प्राप्त कर सकते हैं।

बीएफएस एल्गोरिदम में एक संपत्ति है जो प्रत्येक परत को एक परत निर्दिष्ट करती है, जिसका अर्थ है कि यह एक प्रारंभिक नोड से कितना दूर है। आप अपने शुरुआती बिंदु से शुरू करते हैं और आपकी वर्तमान परत 0 होगी। फिर आप वर्तमान परत (आमतौर पर कतार में रखे गए) से सभी नोड्स का पालन करें और अपने पड़ोसियों को ढूंढने का प्रयास करें (पड़ोसियों की सूची से), जिसमें परत नहीं है असाइन किया गया और आप उन्हें +1 उच्च परत असाइन करें।एक बार जब आप अपना नोड पाते हैं, (जो अभी भी x, y को सीमा जांच (या संपत्ति बूल सीमा) के गुणों के रूप में प्राप्त कर सकता है), अपनी भूलभुलैया की सीमा पर, आप जानते हैं कि यह आपकी परत मान है। यदि आप सटीक तरीके से प्रिंट करना चाहते हैं, तो आपको केवल पीछे हटना होगा (पड़ोसियों की अपनी सूचियों के माध्यम से) जो इस शर्त को पूरा करता है कि प्रत्येक चरण -1 परत कम है। यह अंत से शुरू होने के तरीके को प्रिंट करेगा, लेकिन मुझे यकीन है कि आपको Stack डेटा संरचना से थोड़ी मदद के साथ अपना परिणाम मिल जाएगा :)

Answer 2

आपके पास "सरल" ग्राफ समस्या है। ग्राफ कनेक्टिविटी आपके पास कानूनी चाल है। प्रारंभ नोड आपका लाल बिंदु है। एक टर्मिनल नोड प्राप्त करने के लिए, दिए गए भूलभुलैया के बाहर एक और सर्कल का आविष्कार करें; शून्य लागत के चलते सभी सर्कल में वास्तविक निकास नोड्स को कनेक्ट करें।

अब, डिजस्ट्रा के एल्गोरिदम लागू करें। किया हुआ।

---

समस्या को देखने का एक और तरीका रिकर्सन के साथ है। पुराना स्थान काला चिह्नित करने, लाल बिंदु को ले जाएं। नई स्थिति से पुनरावृत्ति। बाहर निकलने पर लौटें (पथ की लंबाई 1 लौटें) या कोई कानूनी चाल नहीं है (वापसी पथ लंबाई अनंत)। सबसे कम ज्ञात पथ रखें।

क्या वे आपको फंस गए हैं?

Answer 3

एक * खोज एल्गोरिथ्म

(से: https://en.wikipedia.org/wiki/A*_search_algorithm)

निम्नलिखित स्यूडोकोड एल्गोरिथ्म का वर्णन करता है [संदिग्ध - पर चर्चा]:

function A*(start,goal) 
    ClosedSet := {}  // The set of nodes already evaluated. 
    OpenSet := {start} // The set of tentative nodes to be evaluated, initially containing the start node 
    Came_From := the empty map // The map of navigated nodes. 


    g_score := map with default value of Infinity 
    g_score[start] := 0 // Cost from start along best known path. 
    // Estimated total cost from start to goal through y. 
    f_score := map with default value of Infinity 
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal) 

    while OpenSet is not empty 
     current := the node in OpenSet having the lowest f_score[] value 
     if current = goal 
      return reconstruct_path(Came_From, goal) 

     OpenSet.Remove(current) 
     ClosedSet.Add(current) 
     for each neighbor of current 
      if neighbor in ClosedSet 
       continue  // Ignore the neighbor which is already evaluated. 
     tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path. 
     if neighbor not in OpenSet // Discover a new node 
      OpenSet.Add(neighbor) 
     else if tentative_g_score >= g_score[neighbor] 
      continue  // This is not a better path. 

     // This path is the best until now. Record it! 
     Came_From[neighbor] := current 
     g_score[neighbor] := tentative_g_score 
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure 

function reconstruct_path(Came_From,current) 
    total_path := [current] 
    while current in Came_From.Keys: 
     current := Came_From[current] 
     total_path.append(current) 
    return total_path 

इसलिए, जहाँ तक मैं समझता हूं - आप अपने प्रारंभ नोड को लाल बिंदु स्थिति \ केंद्र स्थिति पर सेट कर सकते हैं, और लक्ष्य नोड x = 0 या y = 0 या x = 8 या y = 8 (आप 4 फ़ंक्शन कॉल कर सकते हैं, और न्यूनतम ले सकते हैं)

नोड के लिए ह्युरिस्टिक मूल्यों के लिए - केवल काले अवरुद्ध नोड्स को बहुत अधिक ह्युरिस्टिक मूल्यों को सेट करें, जो उन्हें पहुंचने योग्य नहीं बनाएगा, तो एल्गोरिदम उनके चारों ओर गुजर जाएगा।