I had implemented few TSP algorithms in Java long back (2015). Never thought about visualizations on this. Then I came across this. Yes, another Daniel Shiffman gem.

Few rules to how my implementations will work:

• There will be a starting city (indicated by the solid circle)
• The salesman always comes back to his starting city
• All the cities are connected to each other
• This is symmetric TSP. Which basically means that the distance between two cities is the same in each opposite direction

Algorithms Visualized

The most basic one.

The algorithm Daniel used here is to churn all the possible permutations is Lexicographic Ordering. I am always open to learn something new. And this was new.

The one that I had implemented in Java was using recursion which wouldn't work here. I mean I could calculate all the permutations at first and then loop through them to render the paths, but that would require you to wait for the initial calculations to complete. But with Lexicographic Ordering we can render them in an online fashion.

Word of caution, this is an O(n!) algorithm. So if you choose to run for 15 cities and suppose you are getting 60 fps, you still need 600+ years for this to complete. Not sure any device will run that long. A Dynamic Programming approach.

The mantra is Every sub path of a path of minimum distance is itself of minimum distance.

Functions:

• Let g(x, S) : starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
• c_xy : edge cost ends at x from y

Equations:

• g(x, {}) = c_x1
• g(x, {a}) = c_xa + g(a, {})
• g(x, {a,b}) = min( c_xa + g(a, {b}), c_xb + g(b, {a}) )
• g(x, {a,b,c}) = min( c_xa + g(a, {b,c}), c_xb + g(b, {a,c}), c_xc + g(c, {b,c}) )
• ...and so on

Compute the solutions of all sub problems starting with the smallest. Whenever computing a solution requires solutions for smaller problems using the above recursive equations, look up these solutions which are already computed. To compute a minimum distance tour, use the final equation to generate the lst node, and repeat for the other nodes.

Though this is much faster than the Brute Force approach, it is is exponential in nature. O(2ⁿn²). For 15 cities this will run for an hour (again considering 60 fps). An approximation algorithm.

It's a greedy algorithm where the salesman repeatedly visits the nearest city until all have been visited. Usually not the optimal one.

This is an O(n²) algorithm.

For the visualization, at every vertex I show all the neighbors being checked for the nearest one. Another approximation algorithm.

The idea is to repeat Nearest Neighbor one by one for all the vertices as starting point. Then pick the path with the least total distance among them.

This makes it an O(n³) algorithm.

Here the visualization skips the showing of all neighbors for nearest one and just shows the best selected at that moment. Another greedy algorithm.

The algorithm:

• Pick an edge with the cheapest weight.
• Pick the next cheapest edge such that:
  • New edge doesn't close a smaller circuit.
  • New edge results in three edges coming out of a single vertex.

The edges are sorted according to weights.

Visualization here is straightforward, just color the edges that are picked up one by one till the route is complete. Genetic algorithms are heuristics emulating evolution of life. Central idea being survival of the fittest. The phases are:

• Creating initial population
• Calculating fitness
• Selecting the best genes
• Crossover and Mutation

Daniel's video does a great job of explaining the same.

I read upon it a bit and implemented a more refined (maybe?) version here.

• Cities are the genes here and order of visit is the chromosome
• Fitness is inversely proportional (less the distance travelled, better the chromosome) to the path length of the tour
• Initial population is randomly generated
• Repeat till done:
  • Fitness of the population is calculated. Also the best and worst in the population are noted
  • Rank the population with respect to fitness
  • Create a mating pool. To select parents:
    • Use elitism to select top few so that the best ones survive to the next generation
    • For the rest, use Fitness Proportionate Selection which is nothing but a fitness-weighted probability of being selected
  • Crossover. Randomly select 2 parents from the mating pool, then apply Ordered Crossover. WHAT? In ordered crossover, a subset of the first parent string is randomly selected and then remainder of the route is filled with the genes from the second parent in the order in which they appear, without duplicating any genes in the selected subset from the first parent.
  • Mutation. This is to introduce variations. Based on some determined probability, two vertices in an order are swapped.
  • If the child is not better than the worst of the last generation by some percentage, it is rejected.

The population size is kept at n². The number of generations to run is twice of n. And for each population, the route total distance is calculated. Which makes this implementation an O(n⁴) algorithm. For larger number of cities (100+), the population size and generations to run should be made constant.

Controls

You can change the number of cities for the path.

Click Re-Roll cities to run the algorithms.

Daniels video on Brute Force.

From Wikipedia: Held Karp algorithm.

From Wikipedia: Nearest neighbour algorithm.

Daniels video on Genetic Algorithm.

Geeksforgeeks article on Genetic Algorithm.