Travelling Salesman

This post is currently a draft. It is subject to change and modifications.

The travelling salesman problem is a famous problem in computer science. Basically, there are a number of cities in different locations and you are trying to find the shortest route to visit all of them. But there are some rules you need to follow. After visiting all the cities, you need to come back to the city you started from.

  1. You have to visit all the cities
  2. You cannot visit the same city more than once
  3. After visiting all the cities, you need to return to your starting place

This is an interactive article, you can click on each visualization to refresh it.

First of all, let’s pick 10 random cities to use as an example.

{{}} {{}}

If you draw the path randomly, you will see that it is really inefficient and crosses itself many times.

{{}} {{}}

The greedy approach

A simple attempt to solve the problem is by using a greedy algorithm. It basically works like this.

  1. Pick a starting point
  2. Find the closest city to that point
  3. Go to that city, find the closest point again
  4. Repeat until all cities visited

Hill climbing algorithm

The hill climbing algorithm very simple and works all right for the travelling salesman problem. Here are the steps.

  1. Start with a random solution
  2. Mutate the solution a little
  3. Check if the mutation resulted in a shorter distance or not
  4. Keep the solution if the distance is shorter
  5. Go back to the old solution if not
  6. Repeat

{{}} {{}}


Comments BETA