State-Space Search: Algorithms, Complexity, Extensions, and Applications

by Weixiong Zhang

Overview

This book is about problem solving. Specifically, it is about heuristic state-space search under branch-and-bound framework for solving combinatorial optimization problems. The two central themes of this book are the average-case complexity of heuristic state-space search algorithms based on branch-and-bound, and their applications to developing new problem-solving methods and algorithms. Heuristic state-space search is one of the fundamental problem-solving techniques in Computer Science and Operations Research, and usually constitutes an important component of most intelligent problem-solving systems. The search algorithms considered in this book can be classified into the category of branch-and-bound. Branch-and-bound is a general problem-solving paradigm, and is one of the best techniques for optimally solving computation-intensive problems, such as scheduling and planning. The main search algorithms considered include best-first search, depth­ first branch-and-bound, iterative deepening, recursive best-first search, and space-bounded best-first search. Best-first search and depth-first branch-and-bound are very well known and have been used extensively in Computer Science and Operations Research. One important feature of depth-first branch-and-bound is that it only requires space this is linear in the maximal search depth, making it very often a favorable search algo­ rithm over best-first search in practice. Iterative deepening and recursive best-first search are the other two linear-space search algorithms. Iterative deepening is an important algorithm in Artificial Intelligence, and plays an irreplaceable role in building a real-time game-playing program.

Product Details

ISBN-13:	9780387988320
Publisher:	Springer New York
Publication date:	10/14/1999
Edition description:	1999
Pages:	201
Product dimensions:	6.10(w) x 9.25(h) x 0.02(d)

Table of Contents

1 State-Space Search for Problem Solving.- 1.1 Combinatorial Search Problems.- 1.2 Branch-and-Bound Methods.- 1.3 Bibliographical and Historical Remarks.- 2 Algorithms for Combinatorial Optimization.- 2.1 Algorithms for Optimal Solutions.- 2.2 Algorithms for Approximate Solutions.- 2.3 Bibliographical and Historical Remarks.- 3 Complexity of State-Space Search for Optimal Solutions.- 3.1 Incremental Random Trees.- 3.2 Problem Complexity and Cost of Optimal Goal.- 3.3 Best-First Search.- 3.4 Depth-First Branch-and-Bound.- 3.5 Iterative Deepening.- 3.6 Recursive and Space-Bounded Best-First Searches.- 3.7 Branching Factors.- 3.8 Summary of Search Complexity.- 3.9 Graphs Versus Trees.- 3.10 Bibliographical and Historical Remarks.- 4 Computational Complexity Transitions.- 4.1 Complexity Transition.- 4.2 Anomaly in Sliding-Tile Puzzles.- 4.3 Complexity Transition on the Asymmetric Traveling Salesman Problem.- 4.4 Bibliographical and Historical Remarks.- 5 Algorithm Selection.- 5.1 Comparison on Analytic Model.- 5.2 Comparison on Practical Problems.- 5.3 Summary.- 6 A Study of Branch-and-Bound on the Asymmetric Traveling Salesman Problem.- 6.1 Complexity of Branch-and-Bound Subtour Elimination.- 6.2 Local Search for the Asymmetric Traveling Salesman Problem.- 6.3 Finding Initial Tours.- 6.4 Depth-First Branch-and-Bound Versus Local Search.- 6.5 Bibliographical and Historical Remarks.- 7 State-Space Transformation for Approximation and Flexible Computation.- 7.1 Anytime Approximation Computation.- 7.2 Flexible Computation.- 7.3 State-Space Transformation.- 7.4 Properties of State-Space Transformation.- 7.5 Improvements and Extensions.- 7.6 Learning Edge-Cost Distribution and Branching Factor.- 7.7 Experimental Results.- 7.8 Bibliographical and Historical Remarks.- 8 Forward Pruning for Approximation and Flexible Computation, Part I: Single-Agent Combinatorial Optimization.- 8.1 Forward Pruning.- 8.2 Domain-Independent Pruning Heuristics.- 8.3 Forward Pruning as State-Space Transformation.- 8.4 Analyses.- 8.5 Learning Edge-Cost Distribution and Setting Parameters.- 8.6 Experimental Results.- 8.7 Summary and Discussion.- 8.8 Bibliographical and Historical Remarks.- 9 Forward Pruning for Approximation and Flexible Computation, Part II: Multiagent Game Playing.- 9.1 Minimax and Alpha-Beta Pruning.- 9.2 Forward Pruning.- 9.3 Playing Games.- 9.4 Summary and Discussion.- 9.5 Bibliographical and Historical Remarks.- A Basic Concepts of Branching Processes.- B Mathematical Notation.- C List of Algorithms.- References.