As a prelude to the analysis of the DP algorithm, we present her a simple minded approach to the TSP: we determine the best tour by systematically enumerating all the feasible tours and computing their lengths (time), obviously selecting the one, or rather one, with the shortest tour.
Some of you out there might be surprised to learn that such an algorithm is seriously considered. If you are one of them, I suggest that you read the paper New Constructs for the Description of Combinatorial Optimization Problems in Algebraic Modeling Languages by Bisshop and Fourer [Computational Optimization and Applications, (Exact details will be supplied soon!!!)], where extensions to AMPL are discussed and illustrated.
As you all know, for many years Moshe has maintained that what OR really needs very badly is a branch and bound based enumerative engine!
In any case, for the purposes of this discussion suffice it to say that many useful implicit enumeration schemes are based on primitive complete enumeratation schemes of the type outlined above.
Back to the algorithm.
There are many ways to enumerate all the permutations of a given set of objects. The method considered here was selected because - you guessed!!! - it is very efficient memory-wise. In fact, at any given moment it stores at most two feasible tours:
- the last tour generated.
- the best tour generated thus far.
Purely on administrative grounds we select x=(1,2,3,...,n) as the initial tour. Then in each iteration we generate the next tour in an "increasing lexicographic" using the "digits" {1,2,...,n}. Here is the complete sequence for n=3:
Feasible tours
^^^^^^^^^^^^
[1]: (0,1,2,3,0)
[2]: (0,1,3,2,0)
[3]: (0,2,1,3,0)
[4]: (0,2,3,1,0)
[5]: (0,3,1,2,0)
[6]: (0,3,2,1,0)
Observe that the last tour is always the reverse of the (1,2,...,n), namely the last tour is (n,n-1,..,1).
And here is a machine that generates these sequences for small values of n:
And here is a machine that determines the optimal path for small TSPs based on this simple enumerative scheme. The length of each tour is computed as the tour is generated and the best-so-far tour is updated if necessary.
Well, I have to leave you with this for a while. When I finish marking the exam papers and take care of my garden, I'll add to this directory a 2n DP engine. And after that we shall consider other algorithms as well.