"वर्दी-लागत खोज" एल्गोरिदम में पथ कैसे प्राप्त करें?

Question

मैं वर्दी-लागत खोज के एल्गोरिदम के माध्यम से जा रहा हूं और भले ही मैं पूरी प्राथमिकता कतार प्रक्रिया को समझने में सक्षम हूं, मैं एल्गोरिदम के अंतिम चरण को समझने में सक्षम नहीं हूं।

यदि हम at this graph देखते हैं, तो एल्गोरिदम लागू करने के बाद मेरे पास प्रत्येक नोड के लिए न्यूनतम दूरी होगी, लेकिन मान लीजिए कि मैं ए से जी (उदाहरण की तरह) के बीच पथ जानना चाहता हूं, मैं इसकी गणना कैसे करूं?

Answer 1

आमतौर पर आप प्रत्येक नोड के लिए असीमित कुल लागत के साथ शुरू करते हैं जिसे अभी तक खोजा नहीं गया है। तो फिर तुम एल्गोरिथ्म पूर्ववर्ती को बचाने के लिए एक छोटा सा समायोजित कर सकते हैं:

for each of node's neighbours n 
    if n is not in explored 
     if n is not in frontier 
      frontier.add(n) 
      set n's predecessor to node 
     elif n is in frontier with higher cost 
      replace existing node with n 
      set n's predecessor to node 

बाद में आप सिर्फ पूर्ववर्तियों के अनुक्रम जाँच कर सकते हैं, अपने लक्ष्य से शुरू।

Answer 2

अधिक जानकारी के लिए यात्रा https://www.youtube.com/watch?v=9vNvrRP0ymw

Insert the root into the queue 
While the queue is not empty 
     Dequeue the maximum priority element from the queue 
     (If priorities are same, alphabetically smaller path is chosen) 
     If the path is ending in the goal state, print the path and exit 
     Else 
      Insert all the children of the dequeued element, with the cumulative costs as priority