In [2]:
from IPython.display import Image
This report is intended to answer the question: "How much computation do you need to be to solve a TSP?" Several algorithims exist for solving TSP and it's equivalence. Given a dataset, how close do we come to the optimal tour given several approaches. In this, I'll use several solvers, ranging from the simple, locally greedy algorithm, up to PTAS's that achieve $O(n^{(log n)O(c)}), \epsilon = 1 + \frac{1}{c}$ where $c& is user defined.
I plan to write or re-implement the algorithims, relying heavily on the primitives exposed by networkx
My ending figure of merit is a scatter plot of compute required vs distance from optimal, to compare and contrast several approaches.
WIP
This works by picking a starting node $N$, and choosing the node corresponding to the lowest edge weight that is adjacent to it, if it has not already been visited.
The implementation is provided in code/simple_greed.ipynb.
In [3]:
Image('../code/img/Simple greedy algorithm performance.png')
Out[3]:
The optimal tour for this graph is of length 2579, so this is terrible performance.
The code to run all greedy paths for a fully connected graph with 280 nodes (data/a280.tsp) takes 8.5s to run, meaning that any individual tour takes, on average, 30.36ms.
The time complexity is
https://arxiv.org/pdf/1004.3051.pdf : Prizing on Paths: A PTAS for the Highway Problem. One of the better implementations of the Highway problem
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.165.7929&rep=rep1&type=pdf : Improved Orientations of Physical Networks. The best implementation of the Highway problem, original paper, and how given a few assumptions we can reduce some cases to $O(polylog(n))$ time.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.6594&rep=rep1&type=pdf : Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. The best (comprehensible) Euclidian TSP paper
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.4805&rep=rep1&type=pdf : Guillotine subdivisions approximate polygonal subdivisions: Part II - A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems. THe original paper regarting PTAS's for Euclidian TSP
In [1]:
8.5/280
Out[1]:
In [ ]: