Given a set of cities, find the shortest route that passes through every city and returns to origin.
Yeah, but it's not. It's one of the NP-hard problems (more here), which basically means that we do not have an efficient algorithm to do this. In this app, you can see several different approaches towards this problem.
That one is pretty self-explanatory. The algorithm randomizes a path a given number of times and chooses the best one.
- Select a city and mark it as visited
- Find a closest unvisited city
- Move to this found city and mark it as visited
- Repeat steps 2. and 3. until the path is complete
- Create a random path.
- Find all possible paths created by switching the order of two cities.
- Select the shortest found path.
- Repeat steps 2. and 3. until the best found path is worse than current one (local minimum has been reached).
- Create a random path.
- Switch the order of two random cities.
- If the created path is shorter than current one, select it.
- Otherwise, accept the created path with a probability of
1/Twhere T is current iteration. - Repeat steps 2. and 3. for a given amount of iterations.
- Create a population of random paths.
- Select the best half of the population.
- Create offsprings using a crossover operation, as shown below (P1, P2 are parents, O1 is an offspring).
- Offsprings are mutated with a 20% chance, by switching the order of two random cities.
- Repeat steps 2., 3. and 4. for a given amount of generations.
To run the app, just clone the repo and run: