Heuristic Search
Definition
Heuristic search uses estimation functions or domain knowledge to examine promising states first.
Instead of blindly exploring a search space completely, the method evaluates intermediate states according to a heuristic. For example, A* combines the cost so far with estimated remaining costs.
Simply explained
Like checking roads first that are likely to lead toward the destination in a route search.
Why it matters in practice
Relevant for planning, routing, and search problems with large state spaces.
Example from business
A planning software evaluates possible manufacturing sequences based on estimated remaining time to reduce the search space.
Limits and pitfalls
- Using inadmissible or poor heuristics without verification; equating A* with any heuristic search; measuring runtime advantages without data.
Origin & history
Hart, Nilsson, and Raphael formulated in 1968 with A* a formal basis for using heuristic information in the search for minimal paths.
Use in mid-sized companies
- Possible applications: route planning, scheduling, configuration search, and agent-based planning in clearly modeled state spaces.
Frequently asked questions
Is heuristic search always optimal?
No. For A*, optimality depends among other things on properties of the heuristic. What is the advantage? Often significantly fewer states are examined.
Sources
- Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths · Hart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths
- astar_path · NetworkX, astar_path
- A*-Quellcode · NetworkX, A*-Quellcode
Source verification: 10./11.10.2026.
Editorially reviewed on: