The Travelling Salesman Mathematics

Addition : Examples

If you are familiar with these ideas you could skip it to the part on algorithms. Don't worry this essay is the only mathematics you can also just leave this one it if you like. 

Exponential Growth

This is just for interest's sake to give an idea of how big these numbers become, and how fast they increase. To give an idea how rapid exponential functions start increasing I give examples with n = 1; 2; 4; 8; 10

The exponential function is the product a^n := a x a x … a x a , n-times, illustrated now by a = 5 , 5^1 = 5 ; 5^2 = 5x5 =25 ; 5^4 = 625 ; 5^8 = 309 625 ; 5^10 = 9 765 625 note that if you double n it gives the square. The largest my calculator can give is 5^142 and already is larger than 10^99 i.e. one followed by 99 zeros. With x I mean multiplication. 

The factorial function is defined n! := (n) x (n-1) x (n-2) x … x (2) x (1) and some of the first few factorials are 2! = 2.1 = 2 ;  4! = 4.3.2.1 = 24 ; 8! = 40 320 ; 10! = 10.9.8 .. 2.1 = 3 628 800 , the largest my calculator can handle is 69! = 1.711 .. x 10^98 , so that very soon your scientific calculator could not keep up. Also educational is to plot some graphs.

A basic example

We give another example of a calculation to illustrate exponential time, it is a simple exercise.

Suppose number plates consist of six distinct (digits) numbers like 164352 ; 512364 ; 123456 ; 215634 ; 654321 i.e. no repetition of the plates, distinct licence plates are called permutations and the set is the total number of plates.

In this case for the first place choose one of six digits, the next place you have five then four to choose of and … the last, for the sixth digit there is only one left. The total number of such given licence plates of six digits are  6x5x4x3x2x1 = 6! = 720

A simple Algorithm for the Travelling Salesman Problem

I can think of a very simple very straightforward algorithm to find the solution of a given travelling salesman problem. However it very soon also becomes totally unmanageable with exponential increase as more cities are added.

It is easy to imagine a physical situation as counting the permutations of  {1; 2; 3; … n}
-

1. Systematically number all the possible configurations and calculate the total the distance travelled for each.

2. Compare all distances to find the smallest, its configuration is the solution.

These two given are simple routine algorithms, and that then must be your answer. This is not hard to program at all but as we explained, non-polynomial time programs at this stage are also impractical. In practice the computer would be calculating into eternity as the program runs for exponential time.

An iteration of moves, and respective distances

Label the cities { 1 2 3 … n } in order, a permutation, or { A  B C D … } forming a circuit since in a journey each city has incoming road and an outgoing road and so permutations can be arranged anticlockwise in a circle.  Or half of a parabola. You need to choose the points carefully.

To understand the idea you must draw a sketch, try part of a circle or half of a parabola with the marks arranged anticlockwise. A vector diagram could also help.

Now suppose I start at A, from city A go to to B and then city B to C and C to D resulting in city A to city D.

We compare this to the following route: city A to C and C to B, then B to D, also gives A to D.
-

The two (total) distances are not the same and as on the sketches, therefore a configuration the journey itself results in a change in the total length, as well as this then might be a “move”.

Thus { A B C D } – > { A C B D } where, Length ( A C B D ) > Length ( A B C D )

{ C B } < – > { B C }

This is essentially the idea, there are other considerations also.

Adjacent Transpositions

A transposition in general is simply switching (any) two cities as in effect we have done with the two letters B and C. 

All journeys can be achieved even with a simple exchanging of  two adjacent cities too, and corresponds to a permutation of the labelled cities. Switching C and B otherwise the permutations are the same thus C < – > B.

Every permutation can be reached by a sequence of transpositions, it is not hard to prove. So that theoretically all journeys can be achieved by repeated exchanging in the order of cities, and even as a sequence of adjacent cities only.
-

This is what I propose, as a simple change, an iteration where we choose the “best” transposition and repeat the process with method and discretion. In fact we can reach every possible permutation by using only consecutive adjacent transpositions but it will of course take longer.

The proof is elementary but in practice the process might take forever. Any journey can theoretically be reached by exchanging adjacent cities, if you had enough time and computing power it would although it is not feasible.

However it could mean to find “an exact solution” of the problem, which does exist, is totally impractical. Instead one may in this manner be provided an answer in a much shorter and realistic time. To obtain a “satisfactory solution” or an “acceptable”. Such a proposed method could be based on computer Chess.

Also the theory as in Abstract Algebra would be interesting and might give useful information.