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

Front Cover
Springer Science & Business Media, Oct 14, 1999 - Computers - 201 pages
1 Review
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.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

II
1
III
2
V
4
VI
7
VII
9
VIII
10
IX
11
X
13
LVI
107
LVII
108
LIX
109
LX
110
LXI
112
LXII
114
LXIV
115
LXV
116

XI
14
XII
16
XIII
18
XIV
19
XV
20
XVI
23
XVII
25
XVIII
27
XIX
31
XX
34
XXI
35
XXII
37
XXIII
40
XXIV
41
XXV
45
XXVI
51
XXVII
52
XXVIII
57
XXX
58
XXXI
61
XXXII
62
XXXIII
63
XXXV
67
XXXVI
69
XXXVII
70
XXXVIII
77
XXXIX
81
XL
82
XLI
83
XLII
84
XLIV
86
XLV
87
XLVI
89
XLVII
91
XLVIII
92
XLIX
93
LI
94
LII
96
LIII
103
LIV
104
LV
106
LXVI
117
LXVII
118
LXVIII
120
LXIX
123
LXX
124
LXXI
126
LXXIII
128
LXXIV
130
LXXV
132
LXXVII
136
LXXVIII
139
LXXIX
141
LXXX
142
LXXXI
144
LXXXII
145
LXXXIII
146
LXXXV
147
LXXXVI
148
LXXXIX
149
XC
150
XCIII
156
XCIV
161
XCV
163
XCVI
164
XCVII
165
XCIX
167
C
168
CI
170
CIII
172
CIV
173
CV
175
CVIII
177
CIX
178
CXI
180
CXII
181
CXIII
182
CXIV
185
CXV
186
CXVI
187
CXVII
197
Copyright

Common terms and phrases

Popular passages

Page 188 - P. Cheeseman, B. Kanefsky, and WM Taylor. Where the really hard problems are.
Page 188 - JM Crawford and LD Auton. Experimental results on the crossover point in satisfiability problems.
Page 194 - Fast recursive formulations for best-first search that allow controlled use of memory. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 (Detroit, MI, Aug.), 297-302.
Page 188 - S. Ghose, A. Acharya, and SC de Sarkar, Heuristic search in restricted memory, Artificial Intelligence, Vol.
Page 195 - S. Zilberstein and SJ Russell. Optimal composition of real-time systems. Artificial Intelligence, 82:181-213, 1996.

References to this book

All Book Search results »

Bibliographic information