TSP problem

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

It is an NP-hard problem in combinatorial optimization. We will discuss 2 category of solutions:

  1. Exact algorithms
  2. Heuristic and approximation algorithms

Exact algorithms

  1. Brute force search, which the run time is O(n!), which is impossible for 20 cities.

  2. DP Held–Karp algorithm. O(n^2 x 2^n).

  3. Branch-and-bound algorithm. This can process 40-60 cities.

Heuristic and approximation algorithms

  1. Greedy, or Nearest Neighbour algorithm. (an improved version is called Nearest Fragment algorithm, which connect NN in groups)

  2. Minimum Spanning Tree (MST), build the MST using Kruskal’s algorithm and then do a Depth-first Tree Tour. link to video.

    1. Sort all edges from small to large, then add edges into MST as long as no cycle is created. In the end, a MST is achieved.

    2. Do Depth-first Tree Tour(DFTT)

    3. Length of DFTT is 2 x weight of MST.

    4. Skip some nodes that’s only visited once.

    5. We get an legitimate solution.

Iterative improvement

Now these are the solutions. However we can improve it by doing 2-opt Swap.

It means selecting 2 edges at random. If swapping results in an improvement, then keep it. Keep doing this. link to video.