The Algorithm Design Manual Second Edition

229

Programming Challenges

These programming challenge problems with robot judging are available at

http://www.programming-challenges.com or http://online-judge.uva.es.

6-1. “Freckles” – Programming Challenges 111001, UVA Judge 10034.

6-2. “Necklace” – Programming Challenges 111002, UVA Judge 10054.

6-3. “Railroads” – Programming Challenges 111004, UVA Judge 10039.

6-4. “Tourist Guide” – Programming Challenges 111006, UVA Judge 10199.

6-5. “The Grand Dinner” – Programming Challenges 111007, UVA Judge 10249.

---

7

Combinatorial Search and Heuristic

Methods

We can solve many problems to optimality using exhaustive search techniques,

although the time complexity can be enormous. For certain applications, it may

pay to spend extra time to be certain of the optimal solution. A good example

occurs in testing a circuit or a program on all possible inputs. You can prove the

correctness of the device by trying all possible inputs and verifying that they give

the correct answer. Verifying correctness is a property to be proud of. However,

claiming that it works correctly on all the inputs you tried is worth much less.

Modern computers have clock rates of a few gigahertz, meaning billions of op-

erations per second. Since doing something interesting takes a few hundred in-

structions, you can hope to search millions of items per second on contemporary

machines.

It is important to realize how big (or how small) one million is. One million

permutations means all arrangements of roughly 10 or 11 objects, but not more.

One million subsets means all combinations of roughly 20 items, but not more.

Solving significantly larger problems requires carefully pruning the search space to

ensure we look at only the elements that really matter.

In this section, we introduce backtracking as a technique for listing all possible

solutions for a combinatorial algorithm problem. We illustrate the power of clever

pruning techniques to speed up real search applications. For problems that are too

large to contemplate using brute-force combinatorial search, we introduce heuris-

tic methods such as simulated annealing. Such heuristic methods are important

weapons in any practical algorist’s arsenal.

S.S. Skiena, The Algorithm Design Manual, 2nd ed., DOI: 10.1007/978-1-84800-070-4 7,

c

 Springer-Verlag London Limited 2008

---

7 . 1

B A C K T R A C K I N G