# Greedy Best-First Search

Published
 Completeness - Not complete. The algorithm is vulnerable to infinite loops if repeated states aren't detected. Optimality - Not optimal. Time Complexity - O(bm) Space Complexity - O(bm)

## Visual Example Current Node Frontier
A B3, C4
B3 D1, C4, E5
D1 F0, C4, E5
F0 C4, E5
Goal Node Found

The subscript number associated with each node, for example C4, is the heuristic value of the node.

1. We start from the root node A.
2. We check to see if A is a goal node. It's not, so we add it's children, nodes B3 and C4, to the frontier.
3. We remove node B3 from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D1 and E5, to the frontier.
4. We remove node D1 from the frontier and check if it's a goal node. It's not, so we add it's child, node F0, to the frontier.
5. We remove node F0 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.