Why do admissable heuristics guarantee optimality?

Question

Today in class, my professor introduced us to admissable heuristics, and stated that they guarantee optimality for the A* algorithm.

I asked him to explain it using an extreme example to make it obvious, but he couldn't.

Can someone please help?

Answer 1

We have a list of candidates, right?

And each of them has an ETC (expected total cost) to reach the goal from the starting node (i.e. the cost to reach that node + the expected remaining cost to the goal (the heuristic)).

Now if the expected cost is identical to the actual cost, we'll literally just pick the nodes on the shortest path (well, any of the shortest paths), and nothing else. Since we pick the lowest ETC, it should be pretty obvious why we only pick nodes from the shortest path - anything not on the shortest path will have a higher ETC.

What if the ETC is less than the actual cost? We always pick the lowest ETC, so we may end up picking nodes not on the shortest path. But we can never reach the goal through a path that's not a shortest path because:

• The shortest path has a lower actual cost than any non-shortest path
• The ETC at the goal is the same as the cost to reach the goal via that path (since we're already at the goal, the expected remaining cost is 0)
• The ETC is always less than or equal to the actual total cost on any path
• Thus the ETC on the shortest path is strictly less than the ETC at the goal that was reached via a non-shortest path.

As an example, let's say we have costs as follows: (the cost above / below a node is the expected remaining cost, the cost at an edge is the actual cost)

  0    10  0  100   0
START ---- O ------ GOAL
0 |                 | 100
  O ------ O ------ O
 100  1   100  1   100

So clearly we'd start off visiting the top middle node, since the ETC is 10 (10+0).

Then the goal would be a candidate, with an ETC of 110 (10+100+0).

Then we'd clearly pick the bottom nodes one after the other, followed by the updated goal, since they all have ETC's lower than the ETC of the current goal, i.e. their ETC's are: 100, 101, 102, 102.

So even though the goal was a candidate, we couldn't pick it because there was still a better path out there.