Jak uzyskać ścieżkę w algorytmie "poszukiwania kosztów jednostajnych"?

Question

Przechodziłem przez algorytm z jednolitego wyszukiwania kosztów i mimo że jestem w stanie zrozumieć całą procedurę kolejki priorytetowej, nie jestem w stanie zrozumieć ostatniego etapu algorytmu.

Jeśli spojrzymy na at this graph, po zastosowaniu algorytmu będę mieć minimalną odległość dla każdego węzła, ale przypuśćmy, że chcę znać ścieżkę między A do G (tak jak w przykładzie), jak to obliczyć?

Answer 1

Zazwyczaj rozpoczynamy od nieskończonego kosztu całkowitego dla każdego węzła, który nie został jeszcze zbadany. Następnie można dostosować algorytm trochę zaoszczędzić poprzednika:

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 

Następnie można po prostu sprawdzić kolejność poprzedników, począwszy od swojej bramki.

Answer 2

wizyta uzyskać więcej informacji 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