Probabilistic analysis of the complexity of A*

DOI10.1016/0004-3702(80)90045-4zbMath0447.68068OpenAlexW2011284942MaRDI QIDQ1146526

Judea Pearl, Rina Dechter, Nam Huyn

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0004-3702(80)90045-4

zbMATH Keywords

heuristic searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Artificial intelligence (68T99)

Related Items

New approaches for understanding the asymptotic complexity of \(A^*\) tree searching., The mathematical modeling of heuristics., An upper bound on the time complexity of iterative-deepening-\(A^*\), Heuristic tree search with nonparametric statistical inference methods, Knowledge versus search: a quantitative analysis using A*, Refinements to depth-first iterative-deepening search in automatic theorem proving, Performance of linear-space search algorithms, Performance of linear-space search algorithms, A result on the computational complexity of heuristic estimates for the \(A^*\) algorithm, Average-case analysis of best-first search in two representative directed acyclic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of admissible search algorithms
• On the optimality of A
• Problem representations and formal properties of heuristic search
• The heuristic search under conditions of error
• An admissible and optimal algorithm for searching AND/OR graphs