I'm preparing for an upcoming exam and came across this question on a sheet:
Explain why it is not enough for a heuristic to be admissible to guarantee the discovery of the optimal path, when conducting a graph search using A*.
I've sat thinking about this and tried explaining it but I can't work this out? I've looked at other similar Q's on here but they talk about how admissibility does guarantee optimality.
The basic proof for optimality of A* relies on the fact that:
Say we have two goal states G and G2, where f(G) = f* which is the optimal solution, and G2 is a suboptimal solution.
n is a direct ancestor of G, so will have to be expanded before G.
From admissibility we know that whatever the f(n) is, it must be <= f*.
If we chose to expand G2 before n however, this means f(G2) <= f(n) and therefore f(G2) <= f*.
This contradicts with the earlier statement that f(G2) is suboptimal so f(G2) > f*.
S
/ \
n G2
/
G
To me this proof relies solely on admissibility, and consistency really doesn't have an effect on it. Although the proof relies on f(G) being larger than f(n), which is provided by consistency, admissibility also provides it under this circumstance? As there's no way f(n) could be larger than f(G) unless the heuristic overestimates the distance?
They are wrong. Admissibility is both necessary and sufficient for A* to find the optimal path.
The author is probably confused because runtime optimality (that is, the algorithm working quickly) requires a consistent heuristic.