Weixiong Zhang

State-Space Search (eBook, PDF)

Algorithms, Complexity, Extensions, and Applications

• Format: PDF

Produktbeschreibung

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.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer US
• Seitenzahl: 201
• Erscheinungstermin: 6. Dezember 2012
• Englisch
• ISBN-13: 9781461215387
• Artikelnr.: 44178495

Inhaltsangabe

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.