Inconsistent heuristics in theory and practice

DOI10.1016/j.artint.2011.02.001zbMath1225.68244MaRDI QIDQ646508

Ariel Felner, Jonathan Schaeffer, Uzi Zahavi, Zhifu Zhang, Nathan R. Sturtevant, Robert C. Holte

Publication date: 17 November 2011

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

Full work available at URL: https://doi.org/10.1016/j.artint.2011.02.001

zbMATH Keywords

heuristic search; \(A^{*}; admissible heuristics; IDA^{*}\); inconsistent heuristics

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

The compressed differential heuristic, Heuristic search for one-to-many shortest path queries, Lower bound sets for biobjective shortest path problems, MM: a bidirectional search algorithm that is guaranteed to meet in the middle, Rational deployment of multiple heuristics in optimal state-space search, A framework for analysing state-abstraction methods, Probably bounded suboptimal heuristic search, Heuristics as Markov chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A heuristic search algorithm with modifiable estimate
• Depth-first iterative-deepening: An optimal admissible tree search
• On the complexity of admissible search algorithms
• On the asymptotic performance of IDA
• Duality in permutation state spaces and the dual search algorithm
• Maximizing over multiple pattern databases speeds up heuristic search
• Breadth-first heuristic search
• Real-time heuristic search
• Frontier search
• Generalized best-first search strategies and the optimality of A*
• Search Algorithms Under Different Kinds of Heuristics—A Comparative Study
• Predicting the Performance of IDA* using Conditional Distributions
• Time complexity of iterative-deepening-\(A^{*}\)
• Disjoint pattern database heuristics
• Sorting with fixed-length reversals