I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's Artificial Intelligence: A Modern Approach they say:

The first condition we require for optimality is that $h(n)$ be an admissible heuristic.


A second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for applications of A* to graph search.

Why is consistency only required for A* graph search and not A* tree search? Why are the conditions for optimality different for the two types of search?

  • 4
    $\begingroup$ Think about what the major difference is between traversing a tree and traversing a graph: in a tree there is only one path between two nodes. In a graph there can be many paths between nodes, some of which are more expensive than others. $\endgroup$ – Eric Lippert Sep 28 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.