State-Space Search
Algorithms, Complexity, Extensions, and Applications
Authors: Zhang, Weixiong
Free PreviewBuy this book
- About this book
-
This book is about problem solving. Specifically, it is about heuristic state-space search under branch-and-bound framework for solving com binatorial 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.
- Table of contents (9 chapters)
-
-
State-Space Search for Problem Solving
Pages 1-12
-
Algorithms for Combinatorial Optimization
Pages 13-33
-
Complexity of State-Space Search for Optimal Solutions
Pages 34-60
-
Computational Complexity Transitions
Pages 61-82
-
Algorithm Selection
Pages 83-91
-
Table of contents (9 chapters)
Recommended for you
Bibliographic Information
- Bibliographic Information
-
- Book Title
- State-Space Search
- Book Subtitle
- Algorithms, Complexity, Extensions, and Applications
- Authors
-
- Weixiong Zhang
- Copyright
- 1999
- Publisher
- Springer-Verlag New York
- Copyright Holder
- Springer-Verlag New York, Inc.
- eBook ISBN
- 978-1-4612-1538-7
- DOI
- 10.1007/978-1-4612-1538-7
- Hardcover ISBN
- 978-0-387-98832-0
- Softcover ISBN
- 978-1-4612-7183-3
- Edition Number
- 1
- Number of Pages
- XVI, 201
- Topics
