Algorithms in a Nutshell

Principle: If No Solution Is Evident, Construct a Search

Early pioneers in the field of artificial intelligence (AI) were often characterized as trying to solve problems for which no known solution existed. One of the most common approaches to solve problems was to convert the problem into a search over a (very large) graph. We dedicate an entire chapter to this approach because it is so important, and it is such a general technique for solving numerous problems. Be careful to apply it when no other computational alternative is available, however! You could use the path-finding approach to discover a sequence of element transpositions that starts from an unsorted array (the initial node) and produces a sorted array (the goal node), but you shouldn't use an algorithm with exponential behavior because numerous O(n log n) algorithms exist to sort the data. Table 11-4 shows the path finding algorithms discussed in Chapter 7.

Table 11-4. Chapter 7: Path finding in AI

Algorithm	Best	Average	Worst	Concepts	Page
Depth-First Search	b*d	b d	b d	Stack, Set, Backtracking	182
Breadth-First Search	b d	b d	b d	Queue, Set	190
A*Search	b*d	b d	b d	Priority Queue, Set, Heuristics	195
Minimax	b ply	b ply	b ply	Recursion, Backtracking, Brute Force	208
NegMax	b ply	b ply	b ply	Recursion, Backtracking, Brute Force	214
AlphaBeta	b ply/2	b ply/2	b ply	Recursion, Backtracking, Heuristics	218