Algorithms
Browse the TSP solvers implemented in teeline: exact algorithms, constructive heuristics, local search and metaheuristics — each with docs and, where available, an interactive explainer.
Exact
Guarantee the mathematically optimal tour at exponential cost. Use for small instances (roughly ≤ 30 cities) or as ground truth to benchmark heuristics.
| Name | Complexity | Interactive explainer |
|---|---|---|
| Bellman-Held-Karp | O(2ⁿ · n²) time, O(2ⁿ · n) space | ▶ interactive |
| Branch & Bound | Exponential worst-case; effective pruning often makes it practical for small instances | ▶ interactive |
Constructive
Build a tour from scratch in a single pass — greedy, spanning-tree or clustering-based. Fast and deterministic, they produce a good first tour for local search to polish.
| Name | Complexity | Interactive explainer |
|---|---|---|
| Nearest Neighbor | O(n log n) with KD-tree | ▶ interactive |
| Fourier | O(K_max · epochs · (n + M) log M) per run | ▶ interactive |
| Christofides | O(n²) | ▶ interactive |
| Greedy Edge | O(n² log n) edge sort + O(n² α(n)) scan | ▶ interactive |
| Savings | O(n² log n) edge sort + O(n² α(n)) scan | ▶ interactive |
| Kohonen SOM | O(epochs · N · n) per run | ▶ interactive |
Local search
Start from a tour and keep applying small changes — swaps, relocations, reversals — until no improvement remains. Simple, fast, and the building block of most practical solvers.
| Name | Complexity | Interactive explainer |
|---|---|---|
| 2-opt | O(n²) / pass | ▶ interactive |
| 3-opt | O(n³) / pass | ▶ interactive |
| Or-opt | O(n²) / pass | ▶ interactive |
| Stochastic Hill Climbing | O(epochs · n) | ▶ interactive |
| Lin-Kernighan | O(epochs · n²) | ▶ interactive |
Metaheuristic
Escape local optima with higher-level strategies — populations, simulated annealing, ant colonies, evolutionary pressure — trading more computation for tours that are usually far better than a single local search.
| Name | Complexity | Interactive explainer |
|---|---|---|
| Simulated Annealing | O(epochs · n) | ▶ interactive |
| Tabu Search | O(epochs · n) | ▶ interactive |
| Genetic Algorithm | O(epochs · pop · n) | ▶ interactive |
| Particle Swarm | O(epochs · swarm · n) | ▶ interactive |
| Cuckoo Search | O(epochs · nests · n) | ▶ interactive |
| Flower Pollination | O(epochs · pop · n) | ▶ interactive |
| Gravitational Search | O(epochs · pop²) | ▶ interactive |
| Ant Colony Optimization | O(epochs · ants · n²) | ▶ interactive |