Linear-space best-first search
Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, \textit{Dijkstra}'s single-source shortest-path algorithm, and the \(A^*\) algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do not expand nodes in best- first if the cost function can decrease along a path. We present a linear-space best-first search algorithm (RBFS) that always explores new nodes in best-first order, regardless of the cost function, and expands fewer nodes than iterative deepening with a nondecreasing cost function. On the sliding-tile puzzles, RBFS with a nonmonotonic weighted evaluation function dramatically reduces computation time with only a small penalty in solution cost. In general, RBFS reduces the space complexity of best- first search from exponential to linear, at the cost of only a constant factor in time complexity in our experiments.
- scientific article; zbMATH DE number 519598
- Performance of linear-space search algorithms
- Linear search with bounded resources
- On linear search heuristics
- scientific article; zbMATH DE number 1962001
- Efficient searching with linear constraints
- Best-first minimax search
- A linear space algorithm for the LCS problem
- A note on two problems in connexion with graphs
- An upper bound on the time complexity of iterative-deepening-\(A^*\)
- Depth-first iterative-deepening: An optimal admissible tree search
- Generalized best-first search strategies and the optimality of A*
- Heuristic search in restricted memory
- Heuristic search viewed as path finding in a graph
- scientific article; zbMATH DE number 4162303 (Why is no real title available?)
- scientific article; zbMATH DE number 4164197 (Why is no real title available?)
- scientific article; zbMATH DE number 3967882 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- Real-time heuristic search
- Reducing reexpansions in iterative-deepening search by controlling cutoff bounds
- Memory intensive AND/OR search for combinatorial optimization in graphical models
- On linear search heuristics
- Generalized best first search using single and multiple heuristics
- Agent searching in a tree and the optimality of iterative deepening
- KBFS: K-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
- Heuristic allocation based on a dynamic programming state-space representation
- Subproblem ordering heuristics for AND/OR best-first search
- Rational deployment of multiple heuristics in optimal state-space search
- \(\text{BIDA}^*\): An improved perimeter search algorithm
- WHIRL: A word-based information representation language
- Batch repair actions for automated troubleshooting
- Potential-based bounded-cost search and anytime non-parametric A*
- Memory-limited model-based diagnosis
- Best-first minimax search
- Predicting optimal solution cost with conditional probabilities
- Evaluating the impact of AND/OR search on 0-1 integer linear programming
- Probably bounded suboptimal heuristic search
- Subdimensional expansion for multirobot path planning
- Duality in permutation state spaces and the dual search algorithm
- Anytime search in dynamic graphs
- Parallelizing simulated annealing algorithms based on high-performance computer
- Breadth-first heuristic search
- Time-bounded best-first search for reversible and non-reversible search graphs
- Tie-breaking strategies for cost-optimal best first search
- Space complexity of combinatorial search
- Heuristic search under contract
- Linear-time disk-based implicit graph search
- Frontier search
- A Tutorial on Learning with Bayesian Networks
- A New Proof-Number Calculation Technique for Proof-Number Search
- Weak Proof-Number Search
- Generalized best-first search strategies and the optimality of A*
- Underconstrained knowledge-intensive constraint satisfaction search
- IDB-ADOPT: A Depth-First Search DCOP Algorithm
- Extended breadth-first search algorithm in practice
- KI 2004: Advances in Artificial Intelligence
- Performance of linear-space search algorithms
- Performance of linear-space search algorithms
- Planning as heuristic search
- A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\)
- Minimax real-time heuristic search
- Sokoban: Enhancing general single-agent search methods using domain knowledge
- The \(PN^{*}\)-search algorithm: Application to tsume-shogi
- Planning and control in artificial intelligence: A unifying perspective
- Heuristic search strategies for multiobjective state space search
- Games solved: Now and in the future
- Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search
- Tree search and quantum computation
- Extended beam search for non-exhaustive state space analysis
- Heuristically ordered search in state graphs
- Controlling the learning process of real-time heuristic search
- Weighted A^* search - unifying view and application
This page was built for publication: Linear-space best-first search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685539)
