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?

Extra

How does an admissible heuristic ensure an optimal solution? – Transplant

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.

Transplant

Answer 2

According to this Wikipedia Article:

With a non-admissible heuristic, the A* algorithm could overlook the optimal solution to a search problem...

A good example is given in the article: 15-puzzle problem.

For this particular problem, take a heuristic function that returns the number of misplaced tiles (to move) as the cost to reach the goal (where the whole puzzle is sorted). This is the least number of moves possible although it cannot be an actual solution.

Take this as the current node:

Goal node:

15 and 14 tiles are swapped.

For the node presented in the above figure, it will return 2 (two tiles are misplaced: 15 and 14). This heuristic function is admissible since it does not ignore the most optimal solution (sorting the puzzle with 2 moves--moving 15 and 14 to their right places).

Hence, the heuristic guarantees optimality.

Racket