Rather than the permutation vector approach used in this study, one can also use a graph traversal algorithm to examine all of the paths out of the first vertex, using the standard method of flagging vertices in use. Successful Hamiltonian tours will include all of vertices and also include an edge from the last vertex back to the first.
Traversal based on an adjacency matrix is bounded above by O(nn).
AdjMatrixTSP.java [.txt
copy for browsing]
For completeness, I'll list the permutation vector approach here, which is
bounded above by O(n!). While it does not consider all possible
j,k vertex pairings, it does consider some pairings for which there
is no edge (and prunes the decision tree on that basis).
Permute.java [.txt
copy for browsing]
Traversal based on an adjacency list will never consider j,k
vertex pairing for which there is no edge. Instead it will avoid going
forward if the destination vertex has already been visited.
AdjListTSP.java [.txt
copy for browsing] [.rtf with two pages
of two-column 8-point text]
One can attempt a little bit of best-fit-first processing if the adjacency
list is generated as sorted from shortest to longest. This gives a little
more overhead in initializing the lists, but may allow finding a shorter tour as
the first discovered, allowing more pruning in the decision tree.
SortListTSP.java [.txt
copy for browsing]
Running the programs as given above on the InlandNW_27.txt data set (picture) gives the following table, on a variety of machines.
|
machine (op. sys.) |
adjacency matrix | permutation vector | adjacency list | sorted adj. list | matrix / list | permutation / list | sorted_list / list | |
| acer (Vista) | 712.274 | 394.054 | 173.278 | 112.819 | 4.111 | 2.274 | 0.651 | |
| compaq (XP) | 453.683 | 264.599 | 103.560 | 115.247 | 4.381 | 2.555 | 1.113 | |
| pavilion (XP) | 337.256 | 284.699 | 84.728 | 92.064 | 3.980 | 3.360 | 1.087 | |
| dimension (XP) | 428.131 | 284.108 | 115.898 | 123.027 | 3.694 | 2.451 | 1.062 | |
| gateway (XP) | 332.339 | 239.289 | 76.963 | 81.011 | 4.318 | 3.109 | 1.053 | |
| hydro4 (Linux) | 470.784 | 279.807 | 87.041 | 89.340 | 5.409 | 3.215 | 1.026 | |
| linux2 (Linux) | 306.314 | 181.669 | 68.976 | 71.446 | 4.441 | 2.634 | 1.036 |
Surprise! Once again, in almost all of the environments, the attempt to improve performance by using best-fit-first actually causes a bit of performance degradation.
Final note: branch-and-bound with best-fit-first (i.e., priority queue of states based on shortest path) is amazingly bad! It amounts to a breadth-first traversal. Even if it is fudged into depth-first traversal (primary criterion is to choose longest available path) it still takes 18 times as long as the adjacency list implementation. Implementation is left as an exercise to the masochistic.
