O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required