• A* tree search works well, except that it takes time re-exploring the branches it has already explored. In other words, if the same node has expanded twice in different branches of the search tree, A* search might explore both of those branches, thus wasting time.

• A* Graph Search, or simply Graph Search, removes this limitation by adding this rule: do not expand the same node more than once. Heuristic. Graph search is optimal only when the forward cost between two successive nodes A and B, given by h(A) - h (B), is less than or equal to the backward cost between those two nodes g(A -> B). This property of graph search heuristic is called consistency.

Consistency: h(A) - h(B) <= g(A -> B)

File code