The Algorithm Design Manual Second Edition

7.5

Heuristic Search Methods

Heuristic methods provide an alternate way to approach difficult combinatorial

optimization problems. Backtracking gave us a method to find the best of all pos-

sible solutions, as scored by a given objective function. However, any algorithm

searching all configurations is doomed to be impossible on large instances.

In this section, we discuss such heuristic search methods. We devote the bulk of

our attention to simulated annealing, which I find to be the most reliable method

to apply in practice. Heuristic search algorithms have an air of voodoo about them,

but how they work and why one method might work better than another follows

logically enough if you think them through.

In particular, we will look at three different heuristic search methods: random

sampling, gradient-descent search, and simulated annealing. The traveling salesman

problem will be our ongoing example for comparing heuristics. All three methods

have two common components:

• Solution space representation – This is a complete yet concise description

of the set of possible solutions for the problem. For traveling salesman, the

solution space consists of (n

− 1)! elements—namely all possible circular per-

mutations of the vertices. We need a data structure to represent each element

of the solution space. For TSP, the candidate solutions can naturally be rep-

resented using an array S of n

− 1 vertices, where S

i

defines the (i + 1)st

vertex on the tour starting from v

1

.

• Cost function – Search methods need a cost or evaluation function to ac-

cess the quality of each element of the solution space. Our search heuristic

---

248

7 .

C O M B I N A T O R I A L S E A R C H A N D H E U R I S T I C M E T H O D S

identifies the element with the best possible score—either highest or lowest

depending upon the nature of the problem. For TSP, the cost function for

evaluating a given candidate solution S should just sum up the costs involved,

namely the weight of all edges (S

i

, S

i+1

), where S

n+1

denotes v

1

.