Algorithms in a Nutshell

(^318) | Chapter 11: Epilogue
Sometimes an algorithm is unable to operate without some higher-than-expected
storage. BUCKETSORTshows its ability to sort in linear time simply by storing up
to O(n) extra storage if the input set is uniformly distributed. Given that today’s
modern computers often have very large random access memory present, you
should consider BUCKETSORT even though its memory requirements are so high.
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 prob-
lems. 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(nlogn) algorithms exist to sort the
data. Table 11-4 shows the path finding algorithms discussed in Chapter 7.
Principle: If No Solution Is Evident, Reduce Your Problem
to Another Problem That Has a Solution
Problem reductionis one of the fundamental approaches used by computer scien-
tists and mathematicians in solving problems. As a simple example, suppose you
wanted an algorithm to locate the fourth largest element in a list. Instead of
writing this special-purpose code, you could use any sorting algorithm to sort the
list and then return the fourth element in the sorted list. Using this approach, you
have defined an algorithm whose performance time is O(nlogn); although this is
not the most efficient way to solve the problem—see theselectKthmethod
described in Chapter 4 instead—it is correct.
Chapter 8 presented a set of problems that all seemed related, but there didn’t seem
to be any easy way to tie them all together. It is possible to reduce all of these prob-
lems into linear programming (LP) and use commercially available software
packages, such as Maple, to compute solutions, but the reductions are compli-
cated; in addition, the general-purpose algorithms used to solve LP problems can be
outperformed, often significantly, by the FORD-FULKERSONfamily of algorithms.
Table 11-4. Chapter 7: Path finding in AI
Algorithm Best Average Worst Concepts Page
DEPTH-FIRSTSEARCH bdbd bd Stack, Set, Backtracking 182
BREADTH-FIRSTSEARCH bd bd bd Queue, Set 190
ASEARCH b*dbd bd Priority Queue, Set, Heuristics 195
MINIMAX bply bply bply Recursion, Backtracking, Brute Force 208
NEGMAX bply bply bply Recursion, Backtracking, Brute Force 214
ALPHABETA bply/2 bply/2 bply Recursion, Backtracking, Heuristics 218
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use