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

Zhang, Weixiong

Rilegato

ISBN 10: 0387988327 ISBN 13: 9780387988320

Casa editrice: Springer-Verlag GmbH, 1999

Riassunto

This book is about problem-solving. In particular it is about heuristic state-space search for combinatorial optimization - one of the fundamental problems of computer science. 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. These include best-first search, depth-first branch-and- bound, iterative deepening, recursive best-first search, and constant- space best-first search. Primarily written for researchers in computer science, the author presupposes a basic familiarity with complexity theory. In addition, it is assumed that the reader is familiar with the basic concepts of random variables and recursive functions. Two succesful applications are presented in depth: one is a set of state-space transformation methods which can be used to find approximate solutions qwuickly, and the second is a method called forward estimation for constructing more informative evaluation functions.

Su questo libro

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.

Product Description

Book by Zhang Weixiong

Dettagli dell'edizione

• Editore: Springer-Verlag GmbH
• Data di pubblicazione: 1999
• Lingua: Inglese
• ISBN 10: 0387988327
• ISBN 13: 9780387988320
• Rilegatura: Copertina rigida
• Numero di pagine: 228
• Contatto del produttore: non disponibile
• Persona responsabile: ProductSafety@springernature.com; ProductSafety@springernature.com; ; Poststr. 9; Darmstadt; 64293; Germania