Greedy BestFirst Search
Published
Completeness    Not complete. The algorithm is vulnerable to infinite loops if repeated states aren't detected. 
Optimality    Not optimal. 
Time Complexity    O(b^{m}) 
Space Complexity    O(b^{m}) 
Visual Example

The subscript number associated with each node, for example C_{4}, is the heuristic value of the node.
 We start from the root node A.
 We check to see if A is a goal node. It's not, so we add it's children, nodes B_{3} and C_{4}, to the frontier.
 We remove node B_{3} from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D_{1} and E_{5}, to the frontier.
 We remove node D_{1} from the frontier and check if it's a goal node. It's not, so we add it's child, node F_{0}, to the frontier.
 We remove node F_{0} from the frontier and check if it's a goal node. It is, so we're done.
Algorithm Notes
 Uses a priority queue for the frontier, where each node is sorted by it's heuristic value.
 The heuristic value of a node is computed by the function h(n).

Any function can be a heuristic function, but the heuristic function is often a distance formula that attempts to predict how close a given node is to the goal node.
One example of a distance formula is the Manhattan distance formula.
Return to Articles