## 6.4.8 Probabilistic View of the Traveling Salesman ProblemBefore completing this discussion, we state a very useful result on the expected length of an optimum traveling salesman tour under a Euclidean travel metric. First, it is helpful to make the following observation. Suppose that a
traveling salesman tour has been drawn through n points all of which lie
in a given area A. Suppose now that this area is expanded uniformly m-fold.
This can be done by changing the coordinates (x, y) of every point in A to
(x, y).
The same traveling salesman tour through the same n points as
before will then be "stretched" in length to
times its earlier length,
for the simple reason that every linear segment in A has now been multiplied
by . Thus, quadrup ing, say, the area A in the
manner described above will
only double the length of the given traveling salesman tour. More generally,
we can state that a given traveling salesman tour With this observation, we now turn to the result of interest. Assume that n points are randomly and independently dispersed over an area A with the location of each point determined by a uniform distribution over A (i.e., each point is equally likely to be anywhere in A). Assume further that an optimum traveling salesman tour has been drawn to cover the n points in question, and let L(n, A) be the length of this optimum tour through the n points in A. The following has then been shown to be true whenever the assumptions above hold [BEAR 59]:
Recently, K has been estimated as being approximately equal to 0.765 [STEI 78]. (An earlier set of simulation experiments had led to the estimate K 0.75 [EILO 71].) Like all limit theorems, the one above must be used carefully. For instance,the value of n which is "large enough" (for the quantity 0.765 to provide good approximations to the expected length of the optimal traveling salesman tour) depends on the shape of the area in which the n points are distributed uniformly. For "fairly compact and fairly convex" areas (see also Section 3.7.1) it seems that surprisingly small values of n may be adequate. For example, n = 15 or larger is quite adequate for equilateral triangles, circles, or squares (see [EILO 71]). While the proof of the limit theorem above is difficult, it is quite easy to devise fairly intuitive arguments that lead to results of the form K [EILO 71]. One of our homework problems develops such an argument, which also contains some of the key characteristics of the formal proof of the theorem. The approximation formula 0.765 is a very useful one for:
In closing this section, we note that, as long as points are reasonably well "spread around" over a region, the expression 0.765 often provides good approximations to the length of optimum TSP tours, even in cases when the n points are not quite independently located or when the probability distribution for the location of individual points is not exactly uniform over the region. For instance, it has been estimated that the optimum tour through 48 major cities, one in each of the 48 continental states in the United States, and Washington, D.C., is 10,070 miles long, assuming Euclidean metric [BEAR 59]. Using instead the formula 0.765 with A the area of the continental United States (= 3,022,400 square miles), one obtains 9,310 miles, for an error of only about -7.5 percent, despite the fact that the 49 cities are far from randomly distributed, since most of them are located at the outer boundaries of the region (Atlantic and Pacific coasts, Great Lakes region), with a further disproportionate concentration of almost one third of the cities in a small part of the country (Northeast). R. Karp has written an excellent paper that shows how, through judicious partitioning of the area in which the points lie, good TSP tours can be constructed in problems that may involve thousands of points by taking maximum advantage of the limit theorem of this section [KARP 77]. |