Home

About 

Greedy Best-First Search (GBFS) is a type of informed search algorithms.

GBFS traverses search trees by first exploring nodes that by some admissible heuristic have lowest cost to the goal.

Works on a priority principle of a queue.

Start (initial node) is added to a queue (it's heuristic cost should be greater than that of any of the other nodes).

Initial node is popped from the queue, and checked if it's a goal; if not, GBFS expands it, and adds its children to the priority queue.

(priority queue, by definition, is sorted by, in this case, nodes' heuristic cost values)

Then repeats the same for each node in a queue recursevily, popping up the first one (since it's heuristic cost is lowest).

Checks if it's a goal; if not, adds its children to the queue. Repeats til the goal is found, or queue is empty.

Thus, GBFS algorithm doesn't neccessarily check nodes in the same depth level first, or goes deep to the end of a branch - it follows nodes with lowest heuristic costs.

Algorithm's Metrics:

Completeness:

  * complete - in finite graph, it will eventually explore all possible states

  * incomplete - can get stuck in loops, if visited nodes not tracked; if infinite state space, or if bad heuristic misleads it can to a dead end

Optimality: not optimal - it doesn't take into account actual path cost (g(n)), only heuristic cost (h(n)), so it might take path that looks closers, but it's actually more expensive

b - branching factor; m - maximum depth of a search space

Time Complexity: O(b^m) [can explore nearly entire state space, if heuristic is poor or misleading, and bounce around the graph inefficiently]

Space Complexity: O(b^m) [stores all nodes in memory → can explode quickly, same as BFS or A*]