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 |
No credit card required