Skip to content

A Formal Basis for the Heuristic Determination of Minimum Cost Paths

Peter Hart, Nils J. Nilsson, Bertram Raphael

IEEE Transactions on Systems Science and Cybernetics · 1968 · 13,470 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Hart, P., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/tssc.1968.300136

In text: (Hart et al., 1968)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

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.

  1. A Comprehensive Survey on Graph Neural Networks2020
  2. The Graph Neural Network Model2008
  3. Graph neural networks: A review of methods and applications2020
  4. Depth-First Search and Linear Graph Algorithms1972
  5. Billion-Scale Similarity Search with GPUs2019

Metadata from OpenAlex (CC0). Citations are generated from the published record.