
xii Contents
11. ELEMENTARY SEARCH TECHNIQUES 395
11.1 State Spaces—396
11.2 State Space Search—403
11.2.1 Basic Graph Search Algorithm 403
11.2.2 Informed and Uninformed Search 404
11.3 Exhaustive Search—404
11.3.1 Breadth- rst Search (BFS) 405
11.3.2 Depth- rst Search (DFS) 407
11.3.3 Comparison Between BFS and DFS 410
11.3.4 Depth- rst Iterative Deepening 412
11.3.5 Bidirectional Search 413
11.3.6 Comparison of Basic Uninformed Search Strategies 416
11.4 Heuristic Search—416
11.4.1 Best- rst Search 416
11.4.2 Generalized State Space Search 418
11.4.3 Hill Climbing 418
11.4.4 The A/A* Algorithms 426
11.4.5 Problem Reduction 437
11.4.6 Means-ends