Chapter 4 – Search

4.1  Introduction

4.1.1  Types of Problem

4.1.2  Structuring the Search Space

4.2  Exhaustive Search and Simple Pruning

4.2.1  Depth and Breadth First Search

4.2.2  Comparing Depth and Breadth First Searches

4.2.3  Programming and Space Costs

4.2.4  Iterative Deepening and Broadening

4.2.5  Finding the Best Solution -- Branch and Bound

4.2.6  Graph Search

4.3  Heuristic Search

4.3.1  Hill Climbing and Best First -- Goal-directed Search

4.3.2  Finding the Best Solution -- The {A${}^*$} Algorithm

4.3.3  Inexact Search

4.4  Knowledge-rich Search

4.4.1  Constraint Satisfaction

4.5  Summary

A* algorithm, adversarial search, backtracking, best first search, blind search, branch and bound search, branching factor, breadth first search, closed list, combinatorial explosion, computer chess, constraint propagation, constraint satisfaction, constraints, depth first search, depth of search tree, deterministic, deterministic search, directed graph, domain-independent knowledge, domain-specific knowledge, eight queens problem, Euclidean distance, exponential growth, feasible solution, feasible state, firewalls, fitness landscape, forgetful hill climbing, game playing, game tree, game tree search, generate and test, generations, genes, genetic algorithm, genotype, global minimum, Go, goal state, Gödel, Kurt, graph search, Hardy, Thomas, heuristic evaluation function, heuristic search, hill climbing algorithm, hill climbing with backtracking, hybrid problems, inexact search, iterative broadening, iterative deepening, knowledge-rich search, local minimum, logic, lower bound, magic square, Manhatten block distance, mathematical optimisation, means–ends analysis, minimax search, natural selection, noughts and crosses, open list, optimal, optimisation, partial state, phenotype, plateau, probability, Prolog, pruning, random walk, ridge, satisficing, search horizon, search space, search strategies, search tree, search!optimisation, simulated annealing, solution path, solution state, stuttering in search trees, Towers of Hanoi, travelling salesman problem