A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm

DOI10.1016/0020-0255(84)90009-4zbMath0556.68013OpenAlexW2048550374MaRDI QIDQ761039

Marco Valtorta

Publication date: 1984

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(84)90009-4

zbMATH Keywords

heuristic search algorithmsemantic representationheuristic evaluation function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

A new result on the complexity of heuristic estimates for the \(A^*\) algorithm, Survey on Directed Model Checking, A framework for analysing state-abstraction methods, A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm
• A method for computing heuristics in problem solving
• Probabilistic analysis of the complexity of A*
• On the complexity of admissible search algorithms
• On the optimality of A
• Problem representations and formal properties of heuristic search
• Heuristically guided search and chromosome matching
• Some Recent Results in Heuristic Search Theory