This is well covered in the corresponding chapter of [Russell & Norvig][1] (4?). Check that out for more details. First, let's review the definitions: ----------- Your definitions of admissible and consistent are correct. An *admissible heuristic* is basically just "optimistic". It never overestimates a distance. A *consistent heuristic* is one where you your prior beliefs about the distances between states are self-consistent. That is, you don't think that it it costs 5 from B to the goal, 2 from A to B, and yet 20 from A to the goal. You *are* allowed to be overly optimistic though. So you could believe that it's 5 from B to the goal, 2 from A to B, and 4 from A to the goal. TREE-SEARCH is a general search strategy for searching problems that have a tree structure: that is, it's never possible to "double back" to an earlier state from a later state. This models certain types of games, for instance, like Tic-Tac-Toe. TREE-SEARCH does not remember which states it has already visited, only the "fringe" of states it hasn't visited yet. GRAPH-Search is a general search strategy for searching graph-structured problems, where it's possible to double back to an earlier state, like in Chess (e.g. both players can just move their kings back and forth). To avoid these loops, GRAPH-Search also keeps track of the states that it has processed. For more on Tree vs. Graph search, see the excellent answers on [this question][2]. --------- Okay, now let's talk through the intuition behind the proofs. We want to show that "If h(n) is admissible, A* using TREE-SEARCH is optimal". The usual proof is by contradiction. 1. Assume that A* with TREE-Search and an admissible heuristic was not optimal. 2. Being non-optimal means that the first complete path from the start to the goal discovered by A* (call this **q**) will be longer than some other path **p**, which A* explored up to some state **s**, but no further. 3. Since the heuristic is admissible, the estimated cost of reaching the goal from **s** must be smaller than the true cost. 4. By 3, and the fact that we know how much it cost to reach **s** along **p**, the estimated total cost of **p**, and thus the cost to expand **s** must be smaller than the true cost of **p**. 5. Since the true cost of **p** is smaller than the cost of **q** (by 2), the estimated cost to expand **s** must be smaller than the true cost of **q**. 6. A* always picks the path with the most promising total cost to expand next, and the cost of expanding the goal state is given by the total path length required to reach it. 7. 5 and 6 form a contradiction, so our assumption in 1 must have been incorrect. Therefore A* must be optimal. The GRAPH-SEARCh proof uses a very similar idea, but accounts for the fact that you might loop back around to earlier states. [1]: https://www.amazon.com/Artificial-Intelligence-Modern-Approach-3rd/dp/0136042597 [2]: https://stackoverflow.com/questions/10680180/graph-search-vs-tree-search