A* - Simple graph example - wrong result

Question

I’ve implemented and used A* several times and thought I knew everything there was to know about A*…. Until I encountered this example:

The graph consists of 4 nodes and 6 directed weighted edges. The heuristic is denoted per node by H=…. The heuristic is clearly admissible, so I don't see any problems with that.

The problem is to find the route from start to goal with the minimal total cost. The correct solution is the route taking the edges with the costs 36 and 18.

My implementation of A* performs the following steps(omitting any operations related to the closed list):

• The startnode is {G = 0, H = 200, -> F = 200} and is selected as ‘current node’
• All its neighbours are added to the openlist = {{G=5, H=100, F=105}, {G=36, H=100, F=136}}.
• The new ‘current node’ is selected, which is the node in the open list with smallest F, which is the node with F = 105, the upper node in the image.
• The neighbours of that node are added to the openlist, which then has the elements { {G=36, H=100,F=136}, {G=58,H=0,F=58}}.
• Again a new current node is selected, which is the goal node, so the algorithm terminates and the route with the costs 5 and 53 is selected.

So the implementation produces the wrong result. What in these steps shouldn’t have happened?

Answer 1

For a heuristic to be admissible, it must be bounded from above by the actual cost to the goal. Your heuristic is not admissible and that's why you're getting the wrong answer. See, for instance, the Wikipedia article on A*.