On the complexity of admissible search algorithms

DOI10.1016/0004-3702(77)90002-9zbMath0344.68023OpenAlexW2083105191MaRDI QIDQ1232903

Alberto Martelli

Publication date: 1977

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(77)90002-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

Heuristic search for one-to-many shortest path queries, Utility of pathmax in partial order heuristic search, An upper bound on the time complexity of iterative-deepening-\(A^*\), A new variant of the \(A^*\)-algorithm which closes a node at most once., Heuristic tree search with nonparametric statistical inference methods, Unnamed Item, MM: a bidirectional search algorithm that is guaranteed to meet in the middle, A method for computing heuristics in problem solving, Probabilistic analysis of the complexity of A*, Inconsistent heuristics in theory and practice, Knowledge versus search: a quantitative analysis using A*, Remarks on the \(\mathrm A^{\ast\ast}\) algorithm, Heuristic estimates in shortest path algorithms, Heuristic search strategies for multiobjective state space search, A new bidirectional search algorithm with shortened postprocessing, A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm, A heuristic search algorithm with modifiable estimate, Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization

Cites Work

• The heuristic search under conditions of error
• Heuristic search viewed as path finding in a graph
• Branch-and-Bound Methods: A Survey
• A Note on Dijkstra's Shortest Path Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item