Discrete Algorithmic Mathematics, Third Edition by Maurer Stephen B

Author:Maurer, Stephen B. [Maurer, Stephen B.]
Language: eng
Format: epub
Publisher: A K Peters/CRC Press
Published: 2013-05-17T04:00:00+00:00

386

Chapter 4

Fundamental Counting Methods

for each possible tour. If the cities (other than the salesman’s home city) are la-

beled 1 through n, then there is a one-to-one correspondence between tours and

permutations of 1 to n. For instance, if n = 5, the tour

home, city 2, city 4, city 3, city 5, city 1, home

corresponds to the permutation 24351. So the first step in the brute force approach

of Section 4.2 is to generate all the permutations.

We pointed out that, for n = 50, this approach is well beyond the capacity

of any computer. So what do you do? One alternative is to look for algorithms

which run quickly and find near-optimal solutions. One such algorithm is to choose

a random selection of tours and find the shortest among them. (Random means

that each possible tour is equally likely to be chosen.) This shortest tour among

those chosen probably won’t be the best of all, but in general it will be close to

best. To see this, first suppose you found just one random tour. On average, in

the ranking of all tours from best to worst it would be right in the middle. (For

instance, if there were just three tours and you picked one at random, 1/3 of the

time you would pick the best tour, 1/3 of the time you would pick the second best,

and 1/3 of the time you would pick the worst, so on average you would pick the

second best.) If you found exactly two tours at random, it should be plausible that

the better of them would be, on average, 1/3 of the way down the ranking from

best to worst. Indeed, if you choose n things at random from a collection of N

things, the average rank of your best choice is approximately 1 /( n+1) of the way

down the ranking from rank 1 (best) to rank N (worst). (We say approximately

because the exact average rank depends, among other things, on whether you allow

repetitions in your random selection.) Specifically, if you take 99 random tours,

only about 1/100 of the remaining N − 99 tours are likely to be shorter than the

shortest of your 99. This is true regardless of the size of N . The larger N is, the

more work you have saved by only computing 99 tours.

The point is, it is very valuable to know how to produce a collection of random

permutations. It suffices to know how to produce one random permutation, because

as soon as you know how to produce one, you just repeat the process as many times

as you want (say, 99 times).

Furthermore, you don’t need to take such complicated problems as the Travel-

ing Salesman Problem to see the usefulness of random combinatorial arrangements.

For example, suppose that 100 students have signed up for a course and there is

room for only 50. One fair way to choose the class is to make a random selection.

This means a random combination of 50 things from the total of 100. So you need

an algorithm to produce such random combinations. Note that once you have an

algorithm to produce a random permutation

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.