How does best-first search differ from hill-climbing?

Question

How does best-first search differ from hill-climbing?

Answer 1

Best-first search

BFS is a search approach and not just a single algorithm, so there are many best-first (BFS) algorithms, such as greedy BFS, A* and B*. BFS algorithms are informed search algorithms, as opposed to uninformed search algorithms (such as breadth-first search, depth-first search, etc.), i.e. BFS algorithms make use of domain knowledge that can be encoded into a so-called heuristic function (that's why they are informed!).

Every BFS algorithm defines a so-called evaluation function $f$ of the following form

$$f(n) = g(n) + h(n)$$

for all nodes $n \in V$ (where $V$ is the set of nodes or states of the search space), where

• $g(n)$ is the cost from the start node (of the search) to the node $n$, and

• $h(n)$ (the so-called heuristic, which is the way of including domain knowledge to solve the search problem) is an estimate of the cost of the cheapest path from $n$ to the goal node.

Depending on how you define $f$ and, in particular, the heuristic function $h$, you get different BFS algorithms. For instance, A* is a BFS algorithm where $h$ is an admissible heuristic (i.e. it never overestimates the cost to the goal node). Because of this admissibility property, A* is guaranteed to find the globally optimal solution (i.e. the cheapest path from a start node to the goal node among all paths), but you can ignore this detail.

To apply a BFS algorithm, you need to define the evaluation function and the search space, i.e. the states (or nodes) and their connections. For example, if you want to find the cheapest path from Paris to Madrid, you need to define that Paris is the start node, Madrid the goal node and then you need to define all intermediate nodes between Paris and Madrid, but you also need to define $g$ and $h$.

Hill climbing

Hill climbing (HC) is a general search strategy (so it's also not just an algorithm!). HC algorithms are greedy local search algorithms, i.e. they typically only find local optima (as opposed to global optima) and they do that greedily (i.e. they do not look ahead). The idea behind HC algorithms is that of moving (or climbing) in the direction of increasing value. HC algorithms can be used to solve optimization problems and not just well-defined search problems, i.e. you start from some solution and you move to the best neighboring solution, and then loop.

Best-first search vs hill climbing

• BFS algorithms are informed search algorithms (as opposed to uninformed)
• BFS algorithms need to define the search space and the evaluation function
• Some BFS algorithms (such as A*) are guaranteed to find the best global solution
• HC algorithms are general (i.e. widely applicable) but local and greedy search and optimization algorithms; consequently, they are not generally guaranteed to find the global optimum (but, in practice, they may work well, depending also on the problem).
• HC algorithms do not need to define the search space explicitly (i.e. you do not need to define the start and goal nodes, and so on), but you just need a way of determining the best neighboring solution

Further reading

The book Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig provides more details about these two search approaches. (You can find free copies of this book online).