Traveling Salesman Problem Visualizer

Overview

The Traveling Salesman Problem (TSP) Visualizer demonstrates algorithms for finding the shortest tour visiting all cities exactly once. Compare exact algorithms like branch-and-bound with heuristics like nearest neighbor, 2-opt, and genetic algorithms. Watch as different approaches navigate the exponential search space. Perfect for understanding NP-hard problems, approximation algorithms, and when to use heuristics over exact methods.

Open in new tab

Tips

• TSP is NP-hard: optimal solutions require exponential time for large instances
• Nearest neighbor is fast but may not find optimal tour (greedy approach)
• 2-opt improves tours by swapping edge pairs that reduce total distance
• Genetic algorithms evolve populations of tours using crossover and mutation
• Branch-and-bound can solve small instances (10-15 cities) optimally
• Tour distance is calculated using Euclidean distance between city coordinates
• Compare solution quality vs computation time for different algorithms
• Real applications: circuit board drilling, genome sequencing, delivery routing