Design and Analysis of Algorithms

Problem Solving with a Computer 25

For example, with reference to the ETS algorithm, we know that we have to generate and test (n – 1)!

permutations. With 5 cities, this number is 4! = 24, a reasonable number, but Jayaraman has 21 cities in

his territory. The algorithm may take time corresponding to 20! ≈ 2 × 10

18

steps. If on a fast machine like a

Pentium, a step is executed in 0.1 microsecond, it will require about 7000 years! Therefore we drop ETS like

a piece of burning charcoal. This simple calculation should have convinced us about several aspects:

•

A seemingly simple problem, with a straightforward algorithm is not necessarily effi cient or solvable

in practice;

•

It will be very fruitful to study and analyze algorithms, to identify ...