A result on the computational complexity of heuristic estimates for the A∗ algorithm
Information SciencesPublished 1 October 1984
Marco Valtorta
Citations50
SJR quartileQ1
SJR score1.80
SNIP1.98
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
The performance of a new heuristic search algorithm that uses a formal representation that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of A*, without requiring a human expert to provide it is analyzed.
Abstract
The performance of a new heuristic search algorithm is analyzed. The algorithm uses a formal representation (semantic representation) that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of A∗, without requiring a human expert to provide it. The heuristic is computed by solving less constrained subproblems (auxiliary problems) of the given problem. The new algorithm is shown to be less efficient than the Dijkstra algorithm, according to the complexity measure "number of node expansions." This proves that it is not efficient to compute heuristics for A∗ by solving auxiliary problems with backtracking.
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.
Principles of Artificial Intelligence
3,336 Citations1982Nils J. Nilsson
This classic introduction to artificial intelligence describes fundamental AI ideas that underlie applications such as natural language processing, automatic programming, robotics, machine vision, automatic theorem proving, and intelligent data retrieval.
ACM SIGSOFT Software Engineering NotesLogic for problem solving
1,191 Citations1982Robert Kowalski, Steve Smoliar
This book investigates the application of logic to problem-solving and computer programming and assumes no previous knowledge of these fields, and may be Karl duncker in addition to make difficult fill one of productive.
Elsevier eBooksOn Representations of Problems of Reasoning about Actions
268 Citations1981Saul Amarel
The chapter discusses a specific problem of transportation scheduling to evaluate the effects of alternative formulations of this problem on the expected efficiency of mechanical procedures for solving it and also to examine the processes that come into play when a transition takes place from a given problem formulation into a better one.
Artificial IntelligenceThe nature of heuristics
181 Citations1982Douglas B. Lenat
Builders of expert rule-based systems attribute the impressive performance of their programs to the corpus of knowledge they embody: a large network of facts to provide breadth of scope, and a large array of informal judgmental rules which guide the system toward plausible paths to follow and towards implausible ones.
Artificial IntelligenceOn the complexity of admissible search algorithms
152 Citations1977Alberto Martelli
This paper analyzes the complexity of heuristic search algorithms, i.e. algorithms which find the shortest path in a graph by using an estimate to guide the search and presents a new search algorithm which runs in O(N2) steps in the worst case and which never requires more steps than A*.
Elsevier eBooksA PROBLEM SIMILARITY APPROACH TO DEVISING HEURISTICS: FIRST RESULTS
53 Citations1981John Gaschnig
Evidence of a role for exploiting certain similarities among problems to transfer a heuristic from one problem to another, from an "easier" problem to a "harder" one is presented.
Artificial IntelligenceProbabilistic analysis of the complexity of A∗
47 Citations1980Nam Huyn, Rina Dechter +1 more
This paper analyzes the number of nodes expanded by A∗ as a function of the accuracy of its heuristic estimates by treating the errors h∗ - h as random variables whose distributions may vary over the nodes in the graph.
Information SciencesProblem representations and formal properties of heuristic search
23 Citations1976Gordon J. VanderBrug
The use of heuristic strategies for searching problem spaces of various types of problem representations is discussed, and geometric analysis provides an intuitive alternative to the algebraic analysis which appears in the literature.
Artificial IntelligenceHeuristically guided search and chromosome matching
18 Citations1970Ugo Montanari
A version of the heuristically guided search algorithm presented which is guaranteed to succeed with the minimum amount of storage is presented and is proved to exploit the clustering of chromosome data.
eScholarship (California Digital Library)Natural generation of admissible heuristics
8 Citations1982Dennis Kibler
If a problem space can be represented by a relational production system, then many useful heuristics can be generated by appealing to appropriate abstraction spaces, and this work formalizes the process by which these heuristic are generated.
A Result on the Computational Complexity of Heuristic Estimates for the A Algorithm.
6 Citations1983Marco Valtorta
Toward a Theory of Problem Solving
6 Citations1976Dino Mandrioli, Alberto Sangiovanni‐Vincentelli +1 more
The new research activity, which has been developed within the area of artificial intelligence and within the domain of problem solving, in particular, has awakened the need for a new theoretical effort centered around the notion of problem.