About this visualization
Best-first search is the general scheme behind several famous algorithms: always expand the frontier node with the smallest evaluation f(n). Choose f yourself and the same program becomes uniform-cost search (f = g), greedy search (f = h), A* (f = g + h) or weighted A*.
How it works
- Choose an evaluation function f(n).
- Always expand the frontier node with the smallest f.
- Experiment with f and watch the search change character: thorough and cheap, or fast and risky.
Formulas used
- (UCS) (greedy)
- (A*) (weighted A*)
Worked example
On the Greedy-trap graph, f = h picks the cheap-looking node and ends with cost 15, while f = g + h finds the cost-7 path. Weighted A* (f = g + w·h) still finds the cost-7 path with w = 2, but with w = 5 or more it behaves like greedy and returns cost 15; its path is guaranteed to cost at most w times the optimum when h is admissible.
Enter these numbers in the simulator above to see every step.
Complexity and properties
| Worst case | |
|---|---|
| Space |
Completeness and optimality depend entirely on f. Weighted A* trades optimality (cost ≤ w × optimal) for speed.
When to use it
- Understanding how heuristic search algorithms are related.
- Trading optimality for speed with weighted A*.
- Designing evaluation functions for AI search problems.
Frequently asked questions
What is the difference between best-first search and greedy best-first search?
Best-first search is the general framework for any evaluation function f(n); greedy best-first search is the special case f(n) = h(n).
What is weighted A*?
A* with f = g + w·h and w > 1. It is faster but its solution can cost up to w times the optimum.
Is best-first search optimal?
It depends on f: yes for f = g or for f = g + h with an admissible heuristic; no for f = h.