¿Cómo obtener la ruta en el algoritmo de "búsqueda uniforme de costos"?

Question

He estado revisando el algoritmo de búsqueda de costos uniformes y aunque soy capaz de comprender el procedimiento de cola de prioridad completa, no puedo entender la etapa final del algoritmo.

Si miramos at this graph, después de aplicar el algoritmo tendré la distancia mínima para cada nodo, pero supongamos que quiero saber la ruta entre A y G (como en el ejemplo), ¿cómo voy a calcular eso?

Answer 1

Normalmente se comienza con un costo total infinito para cada nodo que aún no se ha explorado. A continuación, puede ajustar el algoritmo un poco para salvar el predecesor:

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 

Después se puede simplemente comprobar la secuencia de los predecesores, a partir de su objetivo.

Answer 2

Visita para obtener más información 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