TSP Solver

An educational implementation of algorithms to solve the Traveling Salesman Problem, written from scratch in pure C.

Implemented Algorithms

Algorithm	Type	Worst-case
Exhaustive Search	Exact	O(N!)
Exhaustive Search with Pruning	Exact	O(N!)
Held-Karp	Exact	O(N² × 2^N)
Nearest Neighbour	Heuristic	O(N²)
Greedy	Heuristic	O(N³)
Nearest Insertion	Heuristic	O(N³)
Christofides	Heuristic	O(N³)
2-Opt Improvement	Meta-heuristic	O(N³)
Simulated Annealing	Meta-heuristic	O(N³ × multiplier)
Ant Colony Optimization	Meta-heuristic	O(N³ × iterations)
Genetic Algorithm	Meta-heuristic	O(N² × gen × pop)

Plus two lower bound utilities: MST Lower Bound and Held-Karp Lagrangian Relaxation.

git clone https://github.com/nelsonramosua/TSP
cd TSP
make
./TSP_COMPARISON 3    # run first 3 graphs

Or with Docker:

docker pull nelsonramosua/tsp:latest
docker run --rm nelsonramosua/tsp 3

Actual optimal: 9057.46 km