Overview

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.

Full Product Details

Author:   Weixiong Zhang
Publisher:   Springer-Verlag New York Inc.
Imprint:   Springer-Verlag New York Inc.
Edition:   1999 ed.
Dimensions:   Width: 15.50cm , Height: 1.40cm , Length: 23.50cm
Weight:   1.100kg
ISBN:  

9780387988320

ISBN 10:   0387988327
Pages:   201
Publication Date:   14 October 1999
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions