traveling salesman problem

a well-known problem of finite mathematics. In the simplest case it is formulated in the following manner. Given n cities and the distance between each two cities, a traveling salesman starting from some city must visit the other n– 1 cities and return to the starting point. In what order should he visit the cities (once each) so that the total distance covered is minimum?

Problems of this type, associated with touring a number of points and returning to the starting point, include problems of delivering foodstuffs to stores, supplying electricity to consumers, and constructing circular power transmission lines, as well as various problems arising in the automation of wiring. One such problem, for example, is that of finding an optimal program of operation for an automatic milling machine to drill holes at given points in a radio-receiver panel, that is, of finding the order of proceeding through these points such that the length of the path of the drill head is minimal. Here, the beginning of the path need not coincide with its end, but mathematically this problem can be reduced to the simpler problem presented above. Methods of solving the traveling salesman problem essentially consist in scanning and evaluating all possible variants; no efficient algorithm is known.