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

• Tree best-first graphis searchnot complete if there are cycles or if the space is infinite, complete inif there are not or I check for them and the space is finite. Complexity, both time and space, is $O(b^{\min \lbrace m, |S| \rbrace })$.
• Graph is complete for finite state spaces, but not infor infinite ones.ones. TheComplexity, worst-caseboth time and space complexityspace, is $O(b^{\min \lbrace m, |V|S| \rbrace })$.
With

a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching $O(bm)$