All geek questions in one place

How to get the path in the "search at a single cost" algorithm?

I am looking at a uniform cost search algorithm, and although I can understand the whole queue queuing procedure, I cannot understand the final stage of the algorithm.

If we look at this graph , after applying the algorithm, I will have a minimum distance for each node, but suppose I want to know the path between AG (like the example), how can I calculate this?

+6
source share
2 answers

Usually you start with an infinite total cost for all nodes that have not yet been explored. Then you can tweak the algorithm a bit to save the predecessor:

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

After that, you can simply check the sequence of predecessors, starting with your goal.

+10
source

Visit for more information 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
+1
source

Source: https://habr.com/ru/post/927071/

More articles:


All Articles