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

Portada
Springer Science & Business Media, 14 d’oct. 1999 - 201 pàgines
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.
 

Continguts

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
XLVII
89
XLVIII
91
XLIX
92
L
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
LXXXIII
145
LXXXIV
146
LXXXVI
147
LXXXVII
148
LXXXIX
149
XC
150
XCIII
156
XCIV
161
XCV
163
XCVI
164
XCVII
165
XCIX
167
C
168
CI
170
CIII
172
CV
173
CVI
175
CIX
177
CX
178
CXII
180
CXIII
181
CXIV
182
CXV
185
CXVI
186
CXVIII
187
CXIX
197
Copyright

Altres edicions - Mostra-ho tot

Frases i termes més freqüents

Passatges populars

Pàgina 188 - P. Cheeseman, B. Kanefsky, and WM Taylor. Where the really hard problems are.
Pàgina 188 - JM Crawford and LD Auton. Experimental results on the crossover point in satisfiability problems.
Pàgina 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.
Pàgina 188 - S. Ghose, A. Acharya, and SC de Sarkar, Heuristic search in restricted memory, Artificial Intelligence, Vol.
Pàgina 195 - S. Zilberstein and SJ Russell. Optimal composition of real-time systems. Artificial Intelligence, 82:181-213, 1996.

Informació bibliogràfica