How to prove that admissible/consistent heuristics in A* searching method would lead to optimal solution?

user_12754287 0
Viewed 925

we have proved in class that if A* in Tree-Search is optimal, then h(n) is admissible(Admissible Heuristics). If using A* in Graph-Search finds the optimal solution, then h(n) is consistent. We proved the properties of admissible and consistent if we assume that A* can find the optimal solution. This indicates that consistent /admissible are necessary conditions for optimality in Graph/Tree Searching.

However, I am not too sure how to prove that they are also both sufficient conditions as well. I tried to figure it out, but I still could not find a good way to prove it. For example, I am not too sure how to prove that being admissible can lead to optimality in Tree-Searching using A*? And similarly, how to prove that being consistent can lead to optimality in Graph-Searching using A*? Thank you in advance!

This is my first time asking on StackOverflow, sorry if I am not phrasing my question well. : )Thank you in advance!

a-star graph-algorithm
1 Answers

This indicates that consistent /admissible are necessary conditions for optimality in Graph/Tree Searching.

No, it implies they're sufficient conditions. In fact, the converse is not true - it is possible to find cases where a given non-admissible heuristic returns the optimal result for a specific graph (simple counter-example: a tree with only one path will return the optimal path for any heuristic). Thus they are not necessary conditions.

As a side note, 'consistent' implies 'admissible', and trees are a type of graph, so it is enough to prove the "admissible + graph" case, and all four cases (admissible/consistent, tree/graph) are immediately implied.

user_2384190
Related