DSA Hard Optimization
Traveling Salesman Problem
Twelve store stops, one van, back to the depot by 6pm. Brute force is (n−1)!/2 tours: correct on paper, dead at n=20. TSP is the lab where exact DP meets heuristics with a known optimality gap.
Nail the graph contract first (symmetric vs asymmetric, metric or not). Then Held–Karp subset DP, then local search when state no longer fits.
Decision journey
Contract
Visit-once tour? Metric? Directed?
Tiny n
Enumerate; use as oracle.
Held–Karp DP
State = (subset, endpoint).
Heuristics + bound
Construct, improve, report gap.
What actually happens
Naive idea: try all permutations. Breaks: 20! is astronomical; even 15! is beyond casual compute.
Better idea: Held–Karp remembers only which subset was visited and where the path ends: O(n² 2ⁿ) time and O(n 2ⁿ) memory. Still exponential, but usable to ~20–24 with care.
The improved design still fails for delivery fleets with capacities (VRP), time windows, or n=10³ cities: switch to construction + local search and bound the gap.
Invariant (Held–Karp)
dp[S][j] is the cheapest path that starts at a fixed city, visits exactly the cities in S, and ends at j ∈ S. Transitions extend by one unused city.
How to choose a TSP approach
1. n ≤ 12? Enumerate or bit DP freely.
2. n ≤ ~20–24? Held–Karp if memory allows.
3. Larger / live routing? Heuristics with a lower bound and stop budget.
Quantitative check
n=20: 2²⁰ ≈ 1M subsets; n²2ⁿ ≈ 4×10⁸ ops order: often feasible. n=40: 2⁴⁰ ≈ 1T subsets: exact DP is gone without extreme hardware tricks.
TSP Visualizer (Nearest Neighbor)
Step 1 of 0
Total Distance
1. Specify the instance before choosing an algorithm
“TSP” names a family of contracts. An implementation is only correct for the contract it actually enforces. Use a weight matrix w[u][v]; a tour is a permutation beginning at a fixed start vertex with the start appended once more at the end.
Symmetric or asymmetric?
Symmetric TSP has w(u,v) = w(v,u). One-way travel, turn costs, or traffic often produce asymmetric TSP.
Complete or sparse?
A missing edge is not a large edge. Represent it explicitly and report “no tour” when no Hamiltonian cycle exists.
Metric or arbitrary?
Metric TSP is symmetric, non-negative, zero on the diagonal, and obeys the triangle inequality. Guarantees such as MST doubling require this.
Numeric contract?
Negative weights are valid in a finite tour, but break metric assumptions. Accumulate with arbitrary precision or checked arithmetic.
2. Optimization hardness is not verification hardness
Given a proposed tour, check that each vertex appears once and sum its edges in polynomial time.
“Does a tour of cost at most B exist?” is NP-complete. A tour is a compact certificate.
Finding the minimum-cost tour is NP-hard. No polynomial-time exact algorithm is known for general TSP.
How symmetry shrinks the enumeration
Division by two is valid only for symmetric weights. In asymmetric TSP, reversing a tour can change its cost. Branch-and-bound can prune a partial route only with a proven lower bound; “this prefix is already expensive” is safe with non-negative edges, but not with negative edges.
3. Exact baseline: enumerate every tour
Exhaustive search is the reference implementation for tiny test cases. It fixes the start, skips the reverse duplicate only when the matrix is symmetric, treats None/nullas a missing edge, and permits negative weights. Time is O(n!) and recursion/permutation space is O(n).
Python
from itertools import permutations
from typing import Optional
Weight = Optional[int] # None means that the directed edge is absent.
def tsp_brute_force(graph: list[list[Weight]], start: int = 0):
n = len(graph)
if n == 0 or any(len(row) != n for row in graph):
raise ValueError("graph must be a non-empty square matrix")
if not 0 <= start < n:
raise ValueError("start is outside the graph")
if n == 1:
return 0, [start, start]
symmetric = all(graph[u][v] == graph[v][u]
for u in range(n) for v in range(n))
others = [v for v in range(n) if v != start]
best: Optional[tuple[int, list[int]]] = None
for middle in permutations(others):
# A tour and its reverse have equal cost only for symmetric TSP.
if symmetric and len(middle) > 1 and middle[0] > middle[-1]:
continue
tour = [start, *middle, start]
cost = 0
for u, v in zip(tour, tour[1:]):
weight = graph[u][v]
if weight is None:
break
cost += weight
else:
if best is None or cost < best[0]:
best = cost, tour
return best # None means that no Hamiltonian cycle exists.
if __name__ == "__main__":
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0],
]
answer = tsp_brute_force(graph)
assert answer is not None and answer[0] == 80
assert answer[1][0] == answer[1][-1] == 0
print(answer)Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TSPBruteForce {
record Result(BigInteger cost, List<Integer> tour) {}
private static Long[][] graph;
private static boolean[] used;
private static int[] path;
private static int start;
private static boolean symmetric;
private static Result best;
static Result solve(Long[][] weights, int source) {
validate(weights, source);
int n = weights.length;
if (n == 1) return new Result(BigInteger.ZERO, List.of(source, source));
graph = weights;
start = source;
used = new boolean[n];
path = new int[n];
path[0] = source;
used[source] = true;
symmetric = isSymmetric(weights);
best = null;
search(1, BigInteger.ZERO);
return best; // null means that no Hamiltonian cycle exists.
}
private static void search(int depth, BigInteger cost) {
int n = graph.length;
if (depth == n) {
Long closing = graph[path[n - 1]][start];
if (closing == null) return;
if (symmetric && n > 2 && path[1] > path[n - 1]) return;
BigInteger total = cost.add(BigInteger.valueOf(closing));
if (best == null || total.compareTo(best.cost()) < 0) {
List<Integer> tour = new ArrayList<>();
for (int city : path) tour.add(city);
tour.add(start);
best = new Result(total, List.copyOf(tour));
}
return;
}
int previous = path[depth - 1];
for (int next = 0; next < n; next++) {
Long edge = graph[previous][next];
if (used[next] || edge == null) continue;
used[next] = true;
path[depth] = next;
search(depth + 1, cost.add(BigInteger.valueOf(edge)));
used[next] = false;
}
}
private static boolean isSymmetric(Long[][] w) {
for (int u = 0; u < w.length; u++)
for (int v = 0; v < w.length; v++)
if (!java.util.Objects.equals(w[u][v], w[v][u])) return false;
return true;
}
private static void validate(Long[][] w, int source) {
if (w.length == 0 || source < 0 || source >= w.length)
throw new IllegalArgumentException("invalid graph or source");
for (Long[] row : w)
if (row == null || row.length != w.length)
throw new IllegalArgumentException("graph must be square");
}
public static void main(String[] args) {
Long[][] graph = {
{0L, 10L, 15L, 20L}, {10L, 0L, 35L, 25L},
{15L, 35L, 0L, 30L}, {20L, 25L, 30L, 0L}
};
Result result = solve(graph, 0);
assert result != null && result.cost().equals(BigInteger.valueOf(80));
assert result.tour().get(0) == 0 && result.tour().get(4) == 0;
System.out.println(result);
}
}4. Held–Karp: compress prefixes into subset states
Different visit orders can reach the same endpoint after visiting the same set. Their future choices are identical, so retain only the cheapest prefix. This changes factorial enumeration into O(n² · 2ⁿ) time and O(n · 2ⁿ) space, still exponential, but practical far beyond brute force.
State invariant
Invariant: dp[mask][u] is the minimum cost of a path that starts at s, visits exactly the vertices in mask once, and ends at u. A parent pointer stores the predecessor that achieved that minimum, so the optimal witness can be reconstructed.
Why the recurrence is correct
- 1. Base: dp[only s][s] = 0.
- 2. Last-edge split: every state ending at v has some predecessor u.
- 3. Optimal substructure: replacing its prefix with a cheaper prefix to u improves the tour.
- 4. Closure: after all cities are visited, add the edge from the final city to s.
Python
from typing import Optional
Weight = Optional[int] # None is a missing directed edge.
def held_karp(graph: list[list[Weight]], start: int = 0):
n = len(graph)
if n == 0 or any(len(row) != n for row in graph):
raise ValueError("graph must be a non-empty square matrix")
if not 0 <= start < n:
raise ValueError("start is outside the graph")
if n > 22:
raise ValueError("exact subset DP exceeds this implementation's memory budget")
if n == 1:
return 0, [start, start]
size = 1 << n
dp: list[dict[int, int]] = [dict() for _ in range(size)]
parent: dict[tuple[int, int], int] = {}
base = 1 << start
dp[base][start] = 0
for mask in range(size):
if not mask & base:
continue
for u, prefix_cost in list(dp[mask].items()):
for v in range(n):
edge = graph[u][v]
if mask & (1 << v) or edge is None:
continue
next_mask = mask | (1 << v)
candidate = prefix_cost + edge # Python integers do not overflow.
if v not in dp[next_mask] or candidate < dp[next_mask][v]:
dp[next_mask][v] = candidate
parent[next_mask, v] = u
full = size - 1
finish: Optional[tuple[int, int]] = None # (tour cost, last city)
for u, prefix_cost in dp[full].items():
closing = graph[u][start]
if u == start or closing is None:
continue
candidate = prefix_cost + closing
if finish is None or candidate < finish[0]:
finish = candidate, u
if finish is None:
return None
cost, last = finish
reverse_middle: list[int] = []
mask = full
while last != start:
reverse_middle.append(last)
previous = parent[mask, last]
mask ^= 1 << last
last = previous
tour = [start, *reversed(reverse_middle), start]
return cost, tour
if __name__ == "__main__":
graph = [
[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0],
]
result = held_karp(graph)
assert result is not None and result[0] == 80
assert sorted(result[1][:-1]) == [0, 1, 2, 3]
print(result)Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class HeldKarpTSP {
record Result(BigInteger cost, List<Integer> tour) {}
static Result solve(Long[][] graph, int start) {
validate(graph, start);
int n = graph.length;
if (n > 20) throw new IllegalArgumentException("subset DP memory budget exceeded");
if (n == 1) return new Result(BigInteger.ZERO, List.of(start, start));
int size = 1 << n;
BigInteger[][] dp = new BigInteger[size][n]; // null means unreachable.
int[][] parent = new int[size][n];
for (int[] row : parent) Arrays.fill(row, -1);
int base = 1 << start;
dp[base][start] = BigInteger.ZERO;
for (int mask = 0; mask < size; mask++) {
if ((mask & base) == 0) continue;
for (int u = 0; u < n; u++) {
if (dp[mask][u] == null) continue;
for (int v = 0; v < n; v++) {
Long edge = graph[u][v];
if ((mask & (1 << v)) != 0 || edge == null) continue;
int nextMask = mask | (1 << v);
BigInteger candidate = dp[mask][u].add(BigInteger.valueOf(edge));
if (dp[nextMask][v] == null || candidate.compareTo(dp[nextMask][v]) < 0) {
dp[nextMask][v] = candidate;
parent[nextMask][v] = u;
}
}
}
}
int full = size - 1;
BigInteger best = null;
int last = -1;
for (int u = 0; u < n; u++) {
Long closing = graph[u][start];
if (u == start || dp[full][u] == null || closing == null) continue;
BigInteger candidate = dp[full][u].add(BigInteger.valueOf(closing));
if (best == null || candidate.compareTo(best) < 0) {
best = candidate;
last = u;
}
}
if (best == null) return null;
List<Integer> reverseMiddle = new ArrayList<>();
int mask = full;
while (last != start) {
reverseMiddle.add(last);
int previous = parent[mask][last];
mask ^= 1 << last;
last = previous;
}
Collections.reverse(reverseMiddle);
List<Integer> tour = new ArrayList<>();
tour.add(start);
tour.addAll(reverseMiddle);
tour.add(start);
return new Result(best, List.copyOf(tour));
}
private static void validate(Long[][] graph, int start) {
if (graph.length == 0 || start < 0 || start >= graph.length)
throw new IllegalArgumentException("invalid graph or start");
for (Long[] row : graph)
if (row == null || row.length != graph.length)
throw new IllegalArgumentException("graph must be square");
}
public static void main(String[] args) {
Long[][] graph = {
{0L, 10L, 15L, 20L}, {10L, 0L, 35L, 25L},
{15L, 35L, 0L, 30L}, {20L, 25L, 30L, 0L}
};
Result result = solve(graph, 0);
assert result != null && result.cost().equals(BigInteger.valueOf(80));
assert result.tour().size() == 5;
System.out.println(result);
}
}5. Construct quickly: nearest neighbor
Repeatedly take the cheapest outgoing edge to an unvisited city. A deterministic tie-break makes tests reproducible. The algorithm is O(n²) with a matrix, but it is a heuristic, not a proof of quality. On arbitrary weights its result can be unboundedly worse than optimal; even metric instances can defeat a locally attractive first choice. Multi-start nearest neighbor often gives a better seed for local search.
This symmetric matrix gives edges 0–1 = 1, 2–3 = 100, and every other off-diagonal edge = 2. The example violates the triangle inequality, which is precisely why a local choice can hide such a large trap.
Python
from typing import Optional
Weight = Optional[int]
def nearest_neighbor(graph: list[list[Weight]], start: int = 0):
n = len(graph)
if n == 0 or any(len(row) != n for row in graph):
raise ValueError("graph must be a non-empty square matrix")
if not 0 <= start < n:
raise ValueError("start is outside the graph")
if n == 1:
return 0, [start, start]
unvisited = set(range(n)) - {start}
tour = [start]
total = 0
current = start
while unvisited:
choices = [(graph[current][city], city) for city in unvisited
if graph[current][city] is not None]
if not choices:
return None
weight, next_city = min(choices) # cost, then city id: deterministic tie-break.
assert weight is not None
total += weight
tour.append(next_city)
unvisited.remove(next_city)
current = next_city
closing = graph[current][start]
if closing is None:
return None
return total + closing, tour + [start]
if __name__ == "__main__":
graph = [
[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0],
]
result = nearest_neighbor(graph)
assert result == (80, [0, 1, 3, 2, 0])
print(result)Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class NearestNeighborTSP {
record Result(BigInteger cost, List<Integer> tour) {}
static Result solve(Long[][] graph, int start) {
validate(graph, start);
int n = graph.length;
if (n == 1) return new Result(BigInteger.ZERO, List.of(start, start));
boolean[] visited = new boolean[n];
visited[start] = true;
List<Integer> tour = new ArrayList<>();
tour.add(start);
BigInteger total = BigInteger.ZERO;
int current = start;
for (int count = 1; count < n; count++) {
int next = -1;
Long bestEdge = null;
for (int city = 0; city < n; city++) {
Long edge = graph[current][city];
if (visited[city] || edge == null) continue;
if (bestEdge == null || edge < bestEdge || (edge.equals(bestEdge) && city < next)) {
bestEdge = edge;
next = city;
}
}
if (next == -1) return null;
total = total.add(BigInteger.valueOf(bestEdge));
visited[next] = true;
tour.add(next);
current = next;
}
Long closing = graph[current][start];
if (closing == null) return null;
total = total.add(BigInteger.valueOf(closing));
tour.add(start);
return new Result(total, List.copyOf(tour));
}
private static void validate(Long[][] graph, int start) {
if (graph.length == 0 || start < 0 || start >= graph.length)
throw new IllegalArgumentException("invalid graph or start");
for (Long[] row : graph)
if (row == null || row.length != graph.length)
throw new IllegalArgumentException("graph must be square");
}
public static void main(String[] args) {
Long[][] graph = {
{0L, 10L, 15L, 20L}, {10L, 0L, 35L, 25L},
{15L, 35L, 0L, 30L}, {20L, 25L, 30L, 0L}
};
Result result = solve(graph, 0);
assert result != null && result.cost().equals(BigInteger.valueOf(80));
assert result.tour().equals(List.of(0, 1, 3, 2, 0));
System.out.println(result);
}
}6. Improve a tour: symmetric 2-opt
Pick two tour edges (a,b) and (c,d), remove them, reverse the segment from b through c, and reconnect with (a,c) and (b,d). For a symmetric matrix the cost change is only four lookups:Δ = w(a,c) + w(b,d) − w(a,b) − w(c,d). Accepting only negative deltas strictly improves the tour until it reaches a 2-opt local optimum.
The four-edge delta shortcut is not valid for asymmetric TSP: reversing a segment reverses every internal directed edge. Recompute the candidate or use an ATSP-specific neighborhood.
Python
def two_opt(graph: list[list[int]], initial_tour: list[int]):
n = len(graph)
if n == 0 or any(len(row) != n for row in graph):
raise ValueError("graph must be a non-empty square matrix")
if any(graph[u][v] != graph[v][u] for u in range(n) for v in range(n)):
raise ValueError("four-edge delta requires symmetric weights")
if (len(initial_tour) != n + 1 or initial_tour[0] != initial_tour[-1]
or set(initial_tour[:-1]) != set(range(n))):
raise ValueError("initial_tour must be a Hamiltonian cycle")
tour = initial_tour.copy()
while True:
move = None
# Best-improvement scan; fixed start remains at both ends.
for i in range(1, n - 1):
for k in range(i + 1, n):
a, b, c, d = tour[i - 1], tour[i], tour[k], tour[k + 1]
delta = graph[a][c] + graph[b][d] - graph[a][b] - graph[c][d]
if delta < 0 and (move is None or delta < move[0]):
move = delta, i, k
if move is None:
break
_, i, k = move
tour[i:k + 1] = reversed(tour[i:k + 1])
cost = sum(graph[u][v] for u, v in zip(tour, tour[1:]))
return cost, tour
if __name__ == "__main__":
graph = [
[0, 1, 2, 10], [1, 0, 10, 2],
[2, 10, 0, 1], [10, 2, 1, 0],
]
result = two_opt(graph, [0, 1, 2, 3, 0])
assert result == (6, [0, 1, 3, 2, 0])
print(result)Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class TwoOptTSP {
record Result(BigInteger cost, List<Integer> tour) {}
static Result improve(long[][] graph, List<Integer> initialTour) {
validate(graph, initialTour);
int n = graph.length;
List<Integer> tour = new ArrayList<>(initialTour);
while (true) {
BigInteger bestDelta = null;
int bestI = -1, bestK = -1;
for (int i = 1; i < n - 1; i++) {
for (int k = i + 1; k < n; k++) {
int a = tour.get(i - 1), b = tour.get(i);
int c = tour.get(k), d = tour.get(k + 1);
BigInteger added = BigInteger.valueOf(graph[a][c])
.add(BigInteger.valueOf(graph[b][d]));
BigInteger removed = BigInteger.valueOf(graph[a][b])
.add(BigInteger.valueOf(graph[c][d]));
BigInteger delta = added.subtract(removed);
if (delta.signum() < 0 && (bestDelta == null || delta.compareTo(bestDelta) < 0)) {
bestDelta = delta;
bestI = i;
bestK = k;
}
}
}
if (bestDelta == null) break;
Collections.reverse(tour.subList(bestI, bestK + 1));
}
BigInteger cost = BigInteger.ZERO;
for (int i = 0; i + 1 < tour.size(); i++)
cost = cost.add(BigInteger.valueOf(graph[tour.get(i)][tour.get(i + 1)]));
return new Result(cost, List.copyOf(tour));
}
private static void validate(long[][] graph, List<Integer> tour) {
int n = graph.length;
if (n == 0 || tour == null || tour.size() != n + 1)
throw new IllegalArgumentException("invalid graph or tour");
for (long[] row : graph)
if (row == null || row.length != n)
throw new IllegalArgumentException("graph must be square");
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
if (graph[u][v] != graph[v][u])
throw new IllegalArgumentException("2-opt delta requires symmetry");
if (!tour.get(0).equals(tour.get(n))
|| !new HashSet<>(tour.subList(0, n)).equals(new HashSet<>(java.util.stream.IntStream.range(0, n).boxed().toList())))
throw new IllegalArgumentException("tour must visit every city once");
}
public static void main(String[] args) {
long[][] graph = {
{0, 1, 2, 10}, {1, 0, 10, 2},
{2, 10, 0, 1}, {10, 2, 1, 0}
};
Result result = improve(graph, List.of(0, 1, 2, 3, 0));
assert result.cost().equals(BigInteger.valueOf(6));
assert result.tour().equals(List.of(0, 1, 3, 2, 0));
System.out.println(result);
}
}A full best-improvement pass checks O(n²) swaps. The number of improving passes is instance-dependent, so do not label the entire heuristic O(n²). In latency-sensitive systems, cap passes or wall-clock time and return the best tour seen so far.
7. Approximation guarantees need assumptions
| Method | Time | Optimal? | Required assumptions / caveat |
|---|---|---|---|
| Enumeration | O(n!) | Yes | Tiny n; best as an oracle in tests |
| Held–Karp | O(n² · 2ⁿ) | Yes | Memory is usually the first limit |
| Nearest neighbor | O(n²) | No | Fast seed; no constant guarantee for arbitrary weights |
| 2-opt | O(n²) per pass | No | Local optimum depends on seed and neighborhood |
| MST doubling | Polynomial | No, ≤ 2 × OPT | Metric, symmetric TSP only |
| Christofides | Polynomial | No, ≤ 1.5 × OPT | Metric, symmetric TSP only |
The triangle inequality lets an approximation shortcut repeated vertices without increasing cost. Without it, shortcutting can be arbitrarily expensive, so the guarantee disappears even though the code still runs.
8. Choosing and operating a solver
Exact answer required
Use enumeration as a tiny oracle, Held–Karp for modest n, or an integer-programming / branch-and-cut solver for larger structured instances. Record a lower bound as well as the incumbent tour.
Good answer under a deadline
Build several seeds, apply 2-opt or stronger neighborhoods, and use anytime execution: every accepted move leaves a valid incumbent that can be returned when the budget expires.
Real routing constraints
Capacity, time windows, multiple vehicles, optional visits, and live travel times make this a vehicle routing problem, not plain TSP. Model those constraints explicitly instead of hiding them in weights.
Production and test checklist
9. Where the model appears
Routing
A single vehicle must visit required stops and return to its depot. Capacities and time windows move the model into VRP.
Manufacturing
Order drill points, welds, cuts, or robot poses to reduce non-productive tool movement. Direction-dependent setup costs create ATSP.
Warehousing
Sequence pick locations for one tour. Multiple workers, precedence, congestion, and batching add constraints beyond plain TSP.
Scheduling & layout
Sequence jobs with changeover costs or arrange components to minimize transitions. The “cities” need not be geographic.
Mental model
First nail down the graph contract. For tiny n, enumerate and use the result as truth. Held–Karp wins by remembering only which vertices were visited and where the path ends. When exponential state no longer fits, switch the question from “prove optimal” to “construct, improve, bound, and stop on budget.” A fast tour is useful; a fast tour with a validated cost, explicit assumptions, and a known optimality gap is production-quality.
Short takeaway
TSP asks for a minimum closed visit-once tour. Use enumeration or Held–Karp while n is small; beyond that, construct, improve, and report an optimality gap under a clear graph contract.
Exercises
- Why is the Held–Karp state (subset, endpoint) enough, and what would go wrong if you dropped the endpoint?
- n=15 vs n=30: which exact methods die, and what heuristic + bound pair would you ship?
- Give a non-metric cost matrix where a nearest-neighbor tour can be arbitrarily bad relative to OPT (sketch the idea).
Primary sources
- Held & Karp (1962): A dynamic programming approach to sequencing problems.
- Applegate et al., The Traveling Salesman Problem: A Computational Study.
- Cormen et al., CLRS: NP-completeness context; TSP as a classic hard problem.