Performance of linear-space search algorithms

DOI10.1016/0004-3702(94)00047-6zbMath1013.68502OpenAlexW2147872071MaRDI QIDQ5917443

Richard E. Korf, Weixiong Zhang

Publication date: 4 February 2003

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

Full work available at URL: https://doi.org/10.1016/0004-3702(94)00047-6

Mathematics Subject Classification ID

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

Related Items (12)

Memory-limited model-based diagnosis ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Cut-and-solve: An iterative search strategy for combinatorial optimization problems ⋮ Iterative state-space reduction for flexible computation ⋮ Potential-based bounded-cost search and anytime non-parametric A* ⋮ IDB-ADOPT: A Depth-First Search DCOP Algorithm ⋮ Finding optimal solutions to the graph partitioning problem with heuristic search ⋮ Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search ⋮ Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization ⋮ Unifying single-agent and two-player search ⋮ Average-case analysis of best-first search in two representative directed acyclic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Linear-space best-first search
• Depth-first iterative-deepening: An optimal admissible tree search
• Probabilistic analysis of the complexity of A*
• Reducing reexpansions in iterative-deepening search by controlling cutoff bounds
• Postulates for subadditive processes
• The first birth problem for an age-dependent branching process
• Heuristic search in restricted memory
• An upper bound on the time complexity of iterative-deepening-\(A^*\)
• On the asymptotic performance of IDA
• Searching for an optimal path in a tree with random costs
• Real-time heuristic search
• Random Trees and the Analysis of Branch and Bound Procedures
• Stochastic Modeling of Branch-and-Bound Algorithms with Best-First Search
• Generalized best-first search strategies and the optimality of A*
• The average complexity of depth-first search with backtracking and cutoff
• Branch-and-Bound Methods: A Survey
• On a linear diophantine problem of Frobenius

This page was built for publication: Performance of linear-space search algorithms