Passepartout is a fictional character in Jules Verne's novel Le tour du monde en quatre-vingts jours, and I named this repo his name. This repo is some attempts to solve TSP in different ways.
I calculated the optimal path, optimal cost and run time.
- DynamicProgramming_48.c
- Dynamic programming.
- Time Complexity:
O(2^n*n^2)
- Exact solution.
- Approximation.c
- Approximation algorithms.
- Time Complexity:
O(n^3)
- Inexact solution ( smaller than 2 * optimal cost);
- SimulateAnneal_48.c
- Simulated annealing algorithm.
- Exact solution if you run long enough.
- SimulateAnneal_358.c
- Simulated annealing algorithm, too.
- Exact solution if you run long enough.
- att7.txt
- The number of cities is 7. Directed graph, given distance directly.
- att20.txt
- The number of cities is 20. Directed graph, given distance directly.
- bays29.txt
- The number of cities is 20. Directed graph, given distance directly.
- us48.dat
- The number of cities is 48. Undirected graph, given the coordinates of each city.
- att358.dat
- The number of cities is 358. Directed graph.
- Set a large stack space. By the way, I'm using CLion provided by Jet Brains.