Definition
A method that uses problem-specific estimates to guide the search order and reduce the number of candidate states explored.
Heuristic search prioritizes the exploration of candidate states. The 1968 A* paper provided a formal analysis of incorporating heuristic information into minimum-cost path search.
Heuristic search is broader than A*; optimality depends on the conditions satisfied by the algorithm and heuristic function. It can be used for planning and reasoning, as well as for path computation outside artificial intelligence.
Principles and impact
Problems solved
- Reduced the cost of indiscriminately enumerating large numbers of candidate solutions.
Principles
- Combine costs already incurred, estimates of the remaining cost to the goal, or other domain knowledge to choose which states to explore first.
Improvements
Not recorded
Significance
- Made many combinatorial problems more tractable.
History and applications
People
Peter E. Hart、Nils J. Nilsson、Bertram Raphael
Organizations
Not recorded
Events
Not recorded
Applications
Path search、Planning
Limitations
- The state space may still grow rapidly; estimates that do not satisfy the required conditions may lose optimality guarantees.
Upstream and downstream relations
Upstream
No direct upstream relations recorded
Downstream
Sources: A Formal Basis for the Heuristic Determination of Minimum Cost PathsComputer Science as Empirical Inquiry: Symbols and Search