![]() |
For best-first search, the priority queue is sorted according to
an estimate of the optimal cost-to-go. The solutions obtained in this
way are not necessarily optimal; therefore, it does not matter whether
the estimate exceeds the true optimal cost-to-go, which was important
to maintain optimality for search. Although optimal solutions
are not found, in many cases, far fewer vertices are explored, which
results in much faster running times. There is no guarantee, however,
that this will happen. The worst-case performance of best-first
search is worse than that of
search and dynamic programming.
The algorithm is often too greedy because it prefers states that
``look good'' very early in the search. Sometimes the price must be
paid for being greedy! Figure 2.5 shows a contrived
example in which the planning problem involves taking small steps in a
3D world. For any specified number,
, of steps, it is easy to
construct a spiral example that wastes at least
steps in
comparison to Dijkstra's algorithm. Note that best-first search is
not systematic.
Steven M LaValle 2020-08-14