I am investigating the A* search algorithm, and came across this example:

The description of the algorithm is as follows:

Visiting node 0 with currently lowest priority of 8.0

Updating distance of node 1 to 3 and priority to 9.32455532033676

Updating distance of node 2 to 4 and priority to 10.32455532033676

Visiting node 1 with currently lowest priority of 9.32455532033676

Updating distance of node 3 to 9 and priority to 11.82842712474619

Updating distance of node 4 to 13 and priority to 15.82842712474619

Visiting node 2 with currently lowest priority of 10.32455532033676

Visiting node 3 with currently lowest priority of 11.82842712474619

Updating distance of node 5 to 12 and priority to 12.0

Goal node found!

I am wondering how the priority numbers have been derived. Here's the website, where this information was taken from:

https://www.algorithms-and-technologies.com/a_star/r

CodePudding user response：

Euclidean distance is used as heuristic. The actual costs are the labels.

For example at node 1, the G cost is 3 (the edge from node 0) and the H cost is sqrt(2² 6²), making the F cost 9.32455532033676.