-
Notifications
You must be signed in to change notification settings - Fork 4
A* Algorithm
Soumya Sharma edited this page Jul 24, 2020
·
2 revisions
-
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