Introduction

An informed search uses domain-specific hints about the location of goals to find solutions more efficiently than an uninformed strategy.

The hints come in the form of a heuristic function, denoted $h(n)$:

$h(n) =$ stimated cost of the cheapest path from the state at node $n$ to a goal state.

For example, in route-finding problems, we can estimate the distance from the current state to a goal by computing the straight-line distance on the map between the two points.

Greedy best-first search

Greedy best-first search is a form of best-first search that expands first the node with the lowest $h(n)$ value — the node that appears to be closest to the goal — on the grounds that this is likely to lead to a solution quickly. So the evaluation function $f(n) = h(n)$.

Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. The worst-case time and space complexity is $O(\abs{V}|V|)$. With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching $O(bm)$