The DOI matches its Crossref record; 5 of the 7 references it cites were found in a registry or an index.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Abstract
Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Finally, we chose to use A* (Hart, Nilsson, and Raphael 1968) as part of the approach to creating ERCs over other popular algorithms like Monte Carlo Tree Search (Chaslot et al. 2006) due to its more consistent and reproducible behavior.”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
In the citing paper
“A* uses a breadth-first approach to visiting graph nodes and a priority queue based on cost and heuristic values to guide the search towards a specific goal (Hart, Nilsson, and Raphael 1968).”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
In the citing paper
“Unlike breadth-first search, A* is not guaranteed to visit every node in a graph, nor is it guaranteed to find an optimal path without an admissible heuristic, a heuristic function which never over-estimates the distance to the goal (Hart, Nilsson, and Raphael 1968).”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Hart, Nilsson, and Raphael 1968
Citations
Cites
Freimer, M. L., Bellman, R., & Dreyfus, S. E. (1964) · Journal of the American Statistical Association · doi:10.2307/2282884 · Cited by 2,173
Bellman, R., & Dreyfus, S. E. (1962) · Princeton University Press eBooks · doi:10.1515/9781400874651 · Cited by 2,027
The shortest path through a maze
Moore, E. (1959) · Medical Entomology and Zoology · Cited by 756
Solutions of the Shortest-Route Problem—A Review
Pollack, M., & Wiebenson, W. (1960) · Operations Research · doi:10.1287/opre.8.2.224 · Cited by 114
Finite Graphs and Networks, An Introduction with Applications.
Harary, F., Busacker, R. G., & Saaty, T. L. (1967) · American Mathematical Monthly · doi:10.2307/2314099 · Cited by 104
Flagged first, then by citations
2 of the 7 references couldn’t be matched to a known paper.
Research works printed but not linked: 5
- Busacker, 1965, 3
- Gelernter, 1963, Realization of a geometry-theorem proving machine
- Samuel, 1963, Some studies in machine learning using the game of checkers
- 1959, The Annals of the Computation Laboratory of Harvard University, 30
- Feigenbaum, 1963, Computers and Thought
Cited by
Sorted by citations
(1988) · Cited by 16,582
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B. A., Čáp, M., Yong, S. Z., Yershov, D. S., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,601
ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees
Zhang, C., Rabiee, M., Sayyari, E., & Mirarab, S. (2018) · BMC Bioinformatics · doi:10.1186/s12859-018-2129-y · Cited by 2,471
An algorithm for planning collision-free paths among polyhedral obstacles
Lozano‐Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,281
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“Graph search Dijkstra [250], A* [245], State lattice [251] Slow and jerky”
BackgroundMethod
Metadata
- Authors
- Hart, P., Nilsson, N., & Raphael, B.
- Affiliations
- SRI International (US)
- Venue
- IEEE Transactions on Systems Science and Cybernetics
- Published
- 1968
- Volume
- 4
- Issue
- 2
- Pages
- 100-107
- ISSN
- 0536-1567 (ISSN-L)
- OpenAlex
- W1969483458
- Cited by
- 12,738
- References
- 7
- Citations by year
- 2026: 965 · 2025: 1216 · 2024: 1078 · 2023: 893 · 2022: 855 · 2021: 939 · 2020: 707 · 2019: 610 · 2018: 584 · 2017: 493 · 2016: 471 · 2015: 456 · 2014: 437 · 2013: 466 · 2012: 364
- FWCI
- 7.97
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Systems Science and Cybernetics (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Keywords
- least-cost path, shortest path, graph search, heuristic search, search strategies, optimality, heuristic information
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
