Heuristic search viewed as path finding in a graph
Artificial IntelligencePublished 1 January 1970
Ira Pohl
Citations413
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A class of graph-searching procedures is described which uses a heuristic function to guide search, and a number of theoretical results for this model, and the intuition for these results, relate the efficiency of search to the accuracy of the heuristics used.
Abstract
This paper presents a particular model of heuristic search as a path-finding problem in a directed graph. A class of graph-searching procedures is described which uses a heuristic function to guide search. Heuristic functions are estimates of the number of edges that remain to be traversed in reaching a goal node. A number of theoretical results for this model, and the intuition for these results, are presented. They relate the efficiency of search to the accuracy of the heuristic function. The results also explore efficiency as a consequence of the reliance or weight placed on the heuristics used.
Keywords
Computer Science
IEEE Transactions on Systems Science and CyberneticsA Formal Basis for the Heuristic Determination of Minimum Cost Paths
12,265 Citations1968Peter Hart, Nils J. Nilsson +1 more
How heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching is described and an optimality property of a class of search strategies is demonstrated.
IBM Journal of Research and DevelopmentSome Studies in Machine Learning Using the Game of Checkers
4,355 Citations1959Arthur L. Samuel
A new signature-table technique is described together with an improved book-learning procedure which is thought to be much superior to the linear polynomial method and to permit the program to look ahead to a much greater depth than it otherwise could do.
Operations ResearchBranch-and-Bound Methods: A Survey
1,982 Citations1966Eugene L. Lawler, Derek Wood
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
IBM Journal of Research and DevelopmentSome studies in machine learning using the game of checkers
1,418 Citations2000Arthur L. Samuel
Operations ResearchAn Appraisal of Some Shortest-Path Algorithms
997 Citations1969Stuart E. Dreyfus
This paper treats five discrete shortest-path problems: determining the shortest path between two specified nodes of a network, determining the second, third, etc., shortest path, finding the fastest path through a network with travel times depending on the departure time, and finding the shortest paths between specified endpoints that passes through specified intermediate nodes.
Elsevier eBooksGPS, A PROGRAM THAT SIMULATES HUMAN THOUGHT
817 Citations1988Allen Newell, Herbert A. Simon
This work shows that the techniques that have emerged for constructing sophisticated problem-solving programs also provide us with new, strong tools for constructing theories of human thinking that finally reveal with great clarity that the free behavior of a reasonably intelligent human can be understood as the product of a complex but finite and determinate set of laws.
A Mobile Automaton: An Application of Artificial Intelligence Techniques
542 Citations1969Nils J. Nilsson
The main theme of the research is the integration of the necessary planning systems, models of the world, and sensory processing systems into an efficient whole capable of performing a wide range of tasks in a real environment.
Empirical explorations of the logic theory machine
233 Citations1957Allen Newell, James Shaw +1 more
The Logic Theory Machine is devised to learn how it is possible to solve difficult problems such as proving mathematical theorems, discovering scientific laws from data, playing chess, or understanding the meaning of English prose.
Proceedings of the Royal Society of London A Mathematical and Physical SciencesExperiments with the Graph Traverser program
205 Citations1966J. Doran, Donald Michie
An automatic method is described for the solution of a certain family of problems that depends upon the evaluation of intermediate states of the problem according to the extent to which they have features in common with the goal state.
Journal of the ACMSamplesort: A Sampling Approach to Minimal Storage Tree Sorting
163 Citations1970W. D. Frazer, A. C. McKellar
A procedure is proposed which is a generalization of minimal storage tree sorting and which has the following three properties: there is a significant improvement in the expected number of comparisons required to sort the input sequence, the procedure is statistically insensitive to bias in theinput sequence, and the expected numbers of comparisons approaches the information-theoretic lower bound on the number of compared required.
Journal of the ACMExperiments With a Multipurpose, Theorem-Proving Heuristic Program
53 Citations1968James R. Slagle, Philip Bursky
It is hoped that the heuristic program discussed searches for a constructive proof or disproof of a given proposition and uses a search procedure which efficiently selects the seemingly best proposition to work on next.
Proceedings of the National Academy of SciencesON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONS
52 Citations1967S. Winograd
Journal of the ACMSufficient Conditions for the Success of GPS
32 Citations1969George W. Ernst
A formal model of a problem is developed and its relationship to the General Problem Solver (GPS) is discussed and several different formulations of the Tower of Hanoi are given to illustrate the formal concepts.
Journal of the ACMA Formal Deductive Problem-Solving System
32 Citations1968J. R. Quinlan, Earl Hunt
A formalism is defined in which solutions to theorem-proving and similar problems take the form of a sequence of transformations of states into other states, and the FORTRAN Deductive System is shown to be more powerful than the other.
Journal of the ACMA Planning Problem Solver Based on Look-Ahead in Stochastic Game Trees
13 Citations1969Erik Sandewall
International Joint Conference on Artificial IntelligenceConcepts and methods for heuristic search
13 Citations1969Erik Sandewall
It is argued that descriptions of heuristic methods can be significantly compacted if a higher degree of formalization is used.