CODEWITHSUNDEEP
algorithmgraphgreedy
Danny
Danny

Reputation: 379

A* search algorithm with an example

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

enter image description here

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

Upvotes: 0

Views: 364

Answers (1)

user555045
user555045

Reputation: 64913

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.

Upvotes: 2

Related Questions