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

Weixiong Zhang

ISBN 10: 0387988327 / ISBN 13: 9780387988320

Editore: Springer-Verlag New York Inc., 1999

Riguardo questo articolo

This item is printed on demand. New copy - Usually dispatched within 5-9 working days 528. Codice articolo C9780387988320

Dati bibliografici

Titolo: State-Space Search: Algorithms, Complexity, ...

Casa editrice: Springer-Verlag New York Inc.

Data di pubblicazione: 1999

Legatura: Hardback

Condizione: New

Descrizione articolo

Riassunto:

This book is particularly concerned with heuristic state-space search for combinatorial optimization. Its two central themes are the average-case complexity of state-space search algorithms and the applications of the results notably to branch-and-bound techniques. Primarily written for researchers in computer science, the author presupposes a basic familiarity with complexity theory, and it is assumed that the reader is familiar with the basic concepts of random variables and recursive functions. Two successful applications are presented in depth: one is a set of state-space transformation methods which can be used to find approximate solutions quickly, and the second is forward estimation for constructing more informative evaluation functions.

Contenuti:

1 State-Space Search for Problem Solving.- 1.1 Combinatorial Search Problems.- 1.1.1 Sliding-tile puzzles.- 1.1.2 The symmetric Traveling Salesman Problem.- 1.1.3 The asymmetric Traveling Salesman Problem.- 1.1.4 Maximum boolean satisfiability.- 1.2 Branch-and-Bound Methods.- 1.3 Bibliographical and Historical Remarks.- 2 Algorithms for Combinatorial Optimization.- 2.1 Algorithms for Optimal Solutions.- 2.1.1 State space.- 2.1.2 Cost function and heuristic evaluation.- 2.1.3 Best-first search.- 2.1.4 Depth-first branch-and-bound.- 2.1.5 Iterative deepening.- 2.1.6 Recursive best-first search.- 2.1.7 Space-bounded best-first search.- 2.2 Algorithms for Approximate Solutions.- 2.2.1 Approximation based on branch-and-bound.- 2.2.2 Local search.- 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.1.1 Average-case complexity transition.- 4.1.2 Finding all optimal goals.- 4.1.3 Meaning of zero edge cost.- 4.2 Anomaly in Sliding-Tile Puzzles.- 4.3 Complexity Transition on the Asymmetric Traveling Salesman Problem.- 4.3.1 Complexity transitions on the asymmetric Traveling Salesman Problem.- 4.3.2 Identifying the order parameter.- 4.3.3 Summary.- 4.4 Bibliographical and Historical Remarks.- 5 Algorithm Selection.- 5.1 Comparison on Analytic Model.- 5.1.1 Node expansions.- 5.1.2 Running times.- 5.2 Comparison on Practical Problems.- 5.2.1 Lookahead search on sliding-tile puzzles.- 5.2.2 The asymmetric Traveling Salesman Problem.- 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.1.1 A debate over polynomial versus exponential complexity.- 6.1.2 Preliminaries.- 6.1.3 A study of the polynomial argument.- 6.1.4 Summary.- 6.2 Local Search for the Asymmetric Traveling Salesman Problem.- 6.3 Finding Initial Tours.- 6.3.1 Initial tour construction heuristics.- 6.3.2 Problem structures.- 6.3.3 Experimental comparison.- 6.4 Depth-First Branch-and-Bound Versus Local Search.- 6.4.1 Truncated depth-first branch-and-bound versus local search.- 6.4.2 Anytime depth-first branch-and-bound versus local search.- 6.4.3 Discussion.- 6.4.4 Summary.- 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.4.1 Effectiveness.- 7.4.2 Tradeoff between solution quality and computational complexity.- 7.5 Improvements and Extensions.- 7.5.1 Iterative ?-transformation.- 7.5.2 Actual-value pruning.- 7.6 Learning Edge-Cost Distribution and Branching Factor.- 7.7 Experimental Results.- 7.7.1 Random trees.- 7.7.2 The asymmetric Traveling Salesman Problem.- 7.7.3 Maximum boolean satisfiability.- 7.7.4 Summary.- 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.1.1 Forward pruning.- 8.1.2 Complete forward pruning.- 8.1.3 Complete forward pruning for anytime search.- 8.2 Domain-Independent Pruning Heuristics.- 8.2.1 When to prune a node.- 8.2.2 When not to prune a node.- 8.3 Forward Pruning as State-Space Transformation.- 8.4 Analyses.- 8.4.1 An analytic model.- 8.4.2 Probability of finding a solution.- 8.4.3 Modified pruning rule.- 8.4.4 Tradeoff between complexity and solution quality.- 8.4.5 Anytime features.- 8.5 Learning Edge-Cost Distribution and Setting Parameters.- 8.6 Experimental Results.- 8.6.1 Maximum boolean satisfiability.- 8.6.2 The symmetric Traveling Salesman Problem.- 8.6.3 The asymmetric Traveling Salesman Problem.- 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.2.1 Bounds of minimax values.- 9.2.2 Domain-independent pruning heuristics.- 9.3 Playing Games.- 9.3.1 Random game trees.- 9.3.2 The game of Othello.- 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.