Understanding Traveling Salesman Problem Algorithms: Theory and Implem

1. Introduction and Core Concepts

Traveling salesman problem algorithms form one of the most studied and consequential areas in graph theory and combinatorial optimization. At its core, the Traveling Salesman Problem (TSP) asks a deceptively simple question: given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin city? Despite its simple formulation, the problem encapsulates profound computational complexity and has driven decades of research in algorithm design, heuristics, and approximation theory.

The TSP is classified as NP-hard, meaning no known polynomial-time algorithm can solve all instances optimally. This classification is not merely theoretical; it has direct implications for how we approach solving it. Traveling salesman problem algorithms are therefore divided into two broad families: exact algorithms that guarantee an optimal solution but scale poorly, and heuristic or approximation algorithms that trade optimality for computational feasibility. Understanding this trade-off is essential for any software engineer, data scientist, or systems architect who encounters routing, scheduling, or sequencing problems.

The problem is most naturally modeled as a complete weighted graph where vertices represent cities and edge weights represent travel costs, distances, or times. A solution corresponds to a Hamiltonian cycle — a cycle that visits every vertex exactly once — with minimum total weight. When the distance metric satisfies the triangle inequality and symmetry, we refer to it as the metric TSP, which allows for stronger approximation guarantees. The asymmetric variant, where the cost from A to B differs from B to A, models real-world scenarios like one-way streets or wind-dependent flight paths and requires different algorithmic considerations.

Why Traveling Salesman Problem Algorithms Matter

The importance of traveling salesman problem algorithms extends far beyond academic curiosity. TSP is a canonical NP-hard problem, and any efficient solution to it would imply efficient solutions to thousands of other NP-hard problems through polynomial-time reductions. Studying TSP provides a lens for understanding computational intractability, the limits of brute force, and the power of dynamic programming, branch and bound, and metaheuristics.

From a practical standpoint, the ability to reason about TSP directly translates to solving resource-constrained optimization in industry. Whether optimizing delivery routes, minimizing chip wiring length, or scheduling tasks on a single machine, the underlying structure often reduces to finding a low-cost Hamiltonian cycle. Consequently, proficiency in TSP algorithms equips engineers with a versatile toolkit for tackling a wide class of optimization challenges that appear in web infrastructure, logistics, and scientific computing.

2. How It Works

The mechanism behind traveling salesman problem algorithms depends on the chosen strategy, but all share the goal of exploring the permutation space of cities efficiently. The naive approach enumerates all (n-1)!/2 possible tours for a symmetric TSP with n cities, computes each tour's cost, and selects the minimum. While this brute-force method is conceptually straightforward and guarantees optimality, its factorial growth renders it useless beyond n ≈ 12 on modern hardware. This combinatorial explosion motivates more intelligent search and pruning techniques.

Dynamic programming offers a significant improvement through the Held-Karp algorithm. Instead of recomputing overlapping subproblems, Held-Karp defines a state DP[mask][i] as the minimum cost to start at city 0, visit the set of cities represented by bitmask mask, and end at city i. The recurrence builds larger subsets from smaller ones: DP[mask][i] = min over j in mask, j != i of DP[mask without i][j] + dist[j][i]. By memoizing these subproblems, the algorithm reduces time from factorial to exponential O(n² * 2ⁿ), which remains exponential but handles n ≈ 20-25 feasibly and forms the basis for many exact solvers.

Heuristic and approximation algorithms take a fundamentally different approach by constructing a good tour quickly without exhaustive search. The nearest neighbor heuristic greedily builds a tour by always moving to the closest unvisited city, while insertion heuristics start with a small subtour and iteratively insert the remaining cities at the lowest additional cost. More sophisticated methods like 2-opt and 3-opt perform local search: they iteratively improve an existing tour by swapping two or three edges if the swap reduces total length, escaping local optima through repeated perturbations. Lin-Kernighan and Christofides' algorithm provide stronger guarantees by combining minimum spanning trees and perfect matchings.

Exact vs. Approximate Search Paradigms

Exact methods such as branch and bound systematically partition the search space and prune branches that cannot contain an optimal solution. They maintain a global upper bound (best tour found so far) and compute a lower bound for each partial tour, often using the assignment problem relaxation or minimum spanning tree. If the lower bound exceeds the upper bound, the entire subtree is discarded. This pruning can dramatically reduce the explored space for structured instances, though worst-case behavior remains exponential.

Approximation algorithms for metric TSP provide provable guarantees on solution quality. Christofides' algorithm, for example, guarantees a tour at most 1.5 times the optimal length for metric instances. It works by constructing a minimum spanning tree, finding a minimum-weight perfect matching on odd-degree vertices, combining them into an Eulerian graph, and shortcutting an Eulerian tour into a Hamiltonian cycle. Such guarantees are invaluable in production systems where predictable worst-case performance is required, unlike pure heuristics which may produce arbitrarily poor results on pathological inputs.

3. Implementation

Implementing traveling salesman problem algorithms in Python requires careful attention to data representation, state encoding, and performance optimization. The distance matrix is typically represented as a 2D list or NumPy array where dist[i][j] stores the cost between city i and city j. For symmetric instances, dist[i][j] equals dist[j][i], while asymmetric instances require directed weights. Efficient implementations also precompute adjacency and use bitmask integers to represent visited sets for dynamic programming.

Below are four canonical implementations covering exact, dynamic programming, heuristic, and local-search paradigms. All code is written for clarity and includes detailed comments. Note that production implementations would add input validation, early termination, and potentially use libraries like itertools, functools.lru_cache, or NumPy for speed.

import itertools

def tsp_brute_force(dist):
    """
    Exact TSP via brute-force enumeration.
    Fixes start city to 0 to avoid duplicate rotations.
    Returns best tour and its cost.
    """
    n = len(dist)
    best_cost = float('inf')
    best_path = None
    cities = range(1, n)

    # Enumerate all permutations of remaining cities
    for perm in itertools.permutations(cities):
        # Cost from start to first city
        cost = dist[0][perm[0]]
        # Cost between consecutive cities in permutation
        for i in range(len(perm) - 1):
            cost += dist[perm[i]][perm[i+1]]
        # Return to start
        cost += dist[perm[-1]][0]

        # Update best if improved
        if cost < best_cost:
            best_cost = cost
            best_path = (0,) + perm + (0,)

    return best_path, best_cost

# Example usage:
# dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
# print(tsp_brute_force(dist))

def tsp_held_karp(dist):
    """
    Held-Karp dynamic programming algorithm.
    Time: O(n^2 * 2^n), Space: O(n * 2^n)
    Uses bitmask DP to avoid recomputation.
    """
    n = len(dist)
    # dp[mask][i] = min cost to visit cities in mask ending at i
    # mask includes start city 0
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]

    # Base case: start at city 0, only city 0 visited
    dp[1][0] = 0  # mask 1 = 0b...0001

    # Iterate over all subsets
    for mask in range(1 << n):
        for u in range(n):
            # Skip if u not in mask or state unreachable
            if not (mask & (1 << u)):
                continue
            if dp[mask][u] == INF:
                continue
            # Try to extend to unvisited city v
            for v in range(n):
                if mask & (1 << v):
                    continue  # already visited
                new_mask = mask | (1 << v)
                new_cost = dp[mask][u] + dist[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
                    parent[new_mask][v] = u

    # Close the tour by returning to 0
    full_mask = (1 << n) - 1
    best_cost = INF
    last_city = -1
    for i in range(1, n):
        tour_cost = dp[full_mask][i] + dist[i][0]
        if tour_cost < best_cost:
            best_cost = tour_cost
            last_city = i

    # Reconstruct path (optional)
    path = []
    mask = full_mask
    cur = last_city
    while cur != -1:
        path.append(cur)
        nxt = parent[mask][cur]
        mask = mask ^ (1 << cur)
        cur = nxt
    path = list(reversed(path)) + [0]

    return path, best_cost

def tsp_nearest_neighbor(dist, start=0):
    """
    Greedy nearest neighbor heuristic.
    Fast O(n^2) construction, no optimality guarantee.
    Often used to seed local search.
    """
    n = len(dist)
    unvisited = set(range(n))
    unvisited.remove(start)
    tour = [start]
    current = start
    total_cost = 0

    while unvisited:
        # Find closest unvisited city
        next_city = min(unvisited, key=lambda city: dist[current][city])
        total_cost += dist[current][next_city]
        tour.append(next_city)
        unvisited.remove(next_city)
        current = next_city

    # Return to start
    total_cost += dist[current][start]
    tour.append(start)
    return tour, total_cost


def two_opt(tour, dist):
    """
    2-opt local search improvement.
    Repeatedly swaps two edges if it shortens the tour.
    Continues until no improving 2-swap exists.
    """
    n = len(tour) - 1  # tour includes return to start
    improved = True
    best_cost = sum(dist[tour[i]][tour[i+1]] for i in range(n))

    while improved:
        improved = False
        for i in range(1, n - 1):
            for k in range(i + 1, n):
                # Create new tour by reversing segment i..k
                new_tour = tour[:i] + tour[i:k+1][::-1] + tour[k+1:]
                new_cost = sum(dist[new_tour[j]][new_tour[j+1]] for j in range(n))
                if new_cost < best_cost:
                    tour = new_tour
                    best_cost = new_cost
                    improved = True
                    break
            if improved:
                break
    return tour, best_cost

import random

def tsp_genetic(dist, pop_size=100, generations=500, mutation_rate=0.02):
    """
    Genetic algorithm for TSP.
    Maintains population of tours, evolves via crossover and mutation.
    Suitable for large n where exact methods are infeasible.
    """
    n = len(dist)

    def tour_cost(tour):
        cost = 0
        for i in range(n - 1):
            cost += dist[tour[i]][tour[i+1]]
        cost += dist[tour[-1]][tour[0]]
        return cost

    def ordered_crossover(p1, p2):
        # Ordered crossover (OX) preserves relative order
        a, b = sorted(random.sample(range(n), 2))
        child = [-1] * n
        child[a:b+1] = p1[a:b+1]
        # Fill remaining from p2 in order
        idx = (b + 1) % n
        for city in p2:
            if city not in child:
                child[idx] = city
                idx = (idx + 1) % n
        return child

    # Initialize random population
    population = [random.sample(range(n), n) for _ in range(pop_size)]

    for gen in range(generations):
        # Evaluate fitness (lower cost is better)
        population.sort(key=tour_cost)
        next_gen = population[:10]  # elitism: keep top 10

        while len(next_gen) < pop_size:
            p1, p2 = random.sample(population[:50], 2)
            child = ordered_crossover(p1, p2)
            # Mutation: swap two cities with small probability
            if random.random() < mutation_rate:
                i, j = random.sample(range(n), 2)
                child[i], child[j] = child[j], child[i]
            next_gen.append(child)
        population = next_gen

    best = min(population, key=tour_cost)
    return best + [best[0]], tour_cost(best)

4. Step-by-Step Example

To make traveling salesman problem algorithms concrete, consider a small symmetric instance with four cities labeled A, B, C, D. The distance matrix is: A-B 10, A-C 15, A-D 20, B-C 35, B-D 25, C-D 30. We fix A as the start and end point, so we must find the optimal permutation of B, C, D that minimizes total tour length. There are (4-1)! = 6 distinct tours to evaluate.

Enumerating all tours: A-B-C-D-A costs 10 + 35 + 30 + 20 = 95, A-B-D-C-A costs 10 + 25 + 30 + 15 = 80, A-C-B-D-A costs 15 + 35 + 25 + 20 = 95, A-C-D-B-A costs 15 + 30 + 25 + 10 = 80, A-D-B-C-A costs 20 + 25 + 35 + 15 = 95, and A-D-C-B-A costs 20 + 30 + 35 + 10 = 95. The optimal cost is 80, achieved by two tours: A-B-D-C-A and A-C-D-B-A, which are reverse traversals of each other. This symmetry is typical; for undirected graphs, each tour has an identical reverse.

Now observe how Held-Karp builds this solution incrementally. The base state DP[{A}][A] = 0. From there, DP[{A,B}][B] = 10, DP[{A,C}][C] = 15, DP[{A,D}][D] = 20. Next, DP[{A,B,C}][C] = DP[{A,B}][B] + 35 = 45 and DP[{A,B,C}][B] = DP[{A,C}][C] + 35 = 50. Similarly, DP[{A,B,D}][D] = 10 + 25 = 35 via B, DP[{A,B,D}][B] = 20 + 25 = 45 via D, and so on. For the full set {A,B,C,D}, we compute DP[{A,B,C,D}][C] = min(DP[{A,B,D}][B]+35, DP[{A,B,D}][D]+30) = min(45+35, 35+30) = 65, and DP[{A,B,C,D}][D] = min(DP[{A,B,C}][B]+25, DP[{A,B,C}][C]+30) = min(50+25,45+30)=75. Closing each to A yields 65+15=80 and 75+20=95, confirming the optimum 80 ending at C via the path A-B-D-C-A.

Tracing a Heuristic Execution

Running the nearest neighbor heuristic starting at A selects the closest unvisited city at each step. From A, the distances are B 10, C 15, D 20, so it picks B. From B, unvisited are C 35 and D 25, so it picks D. From D, only C remains at 30, so it goes D to C, then C back to A at 15, yielding tour A-B-D-C-A with cost 80 — optimal in this case by luck. However, this is not guaranteed. If we started at B, nearest neighbor would produce B-A-C-D-B costing 10+15+30+25=80 also optimal, but on other matrices it can be substantially worse.

Applying 2-opt to a suboptimal initial tour such as A-B-C-D-A (cost 95) demonstrates local improvement. The algorithm examines all pairs of edges, for instance edges B-C and D-A, and considers reconnecting as B-D and C-A. Swapping edges B-C (35) and D-A (20) for B-D (25) and C-A (15) changes cost by -15, producing A-B-D-C-A with cost 80. Since no further 2-swap improves this tour, the algorithm terminates at the global optimum for this tiny instance, though for larger n it may converge to a local optimum that is not globally optimal.

5. Complexity Analysis

Complexity analysis is central to choosing among traveling salesman problem algorithms because the problem's hardness forces explicit trade-offs between time, space, and solution quality. Exact algorithms guarantee optimality but suffer exponential scaling, while polynomial-time heuristics sacrifice guarantees for speed. Understanding best, average, and worst-case behavior allows engineers to select an appropriate method for a given instance size and service-level requirement.

Brute force enumeration evaluates all (n-1)!/2 tours for symmetric TSP, each in O(n) time to sum edge weights, yielding O(n!) time and O(n) space for the current permutation. Held-Karp improves this to O(n² * 2ⁿ) time and O(n * 2ⁿ) space by memoizing subsets, which is still exponential but dramatically faster for n up to 25. Branch and bound has exponential worst-case time O(n!) but often performs much better on structured data where pruning is effective; its average case depends heavily on the tightness of lower bounds and is instance-dependent.

Heuristics and approximations operate in polynomial time. Nearest neighbor runs in O(n²) time and O(n) space, simply scanning for the minimum edge at each step. 2-opt local search has O(n²) time per iteration and may require an exponential number of iterations in the worst case, though in practice it converges quickly and is often capped at a fixed iteration limit. Christofides' algorithm runs in O(n³) time due to the blossom algorithm for minimum-weight perfect matching and O(n²) space, while genetic algorithms run in O(pop_size * generations * n) time with O(pop_size * n) space, where parameters are tunable.

* Branch and bound average case is highly data-dependent; with strong lower bounds it often explores far fewer than 2ⁿ nodes, but pathological instances approach factorial time. For genetic algorithms, g = generations and p = population size. The key takeaway is that no known algorithm achieves polynomial time for exact solutions, which is consistent with NP-hardness, so practical deployments must choose between exact methods for small n and approximations for large n.

6. Variations and Optimizations

The classic TSP has numerous variations that model different constraints encountered in real deployments. The metric TSP assumes the distance function satisfies triangle inequality and symmetry, enabling the 1.5-approximation of Christofides. The asymmetric TSP (ATSP) relaxes symmetry, requiring directed graphs and often solved by transforming to symmetric TSP or using specialized branch-and-bound with assignment relaxations. The bottleneck TSP minimizes the longest edge in the tour rather than total length, useful for minimizing maximum latency.

Constrained variants add practical realism. The TSP with Time Windows (TSPTW) requires each city to be visited within a specified interval, common in delivery scheduling. The Prize-Collecting TSP allows skipping cities at a penalty, balancing travel cost against profit. The Multiple TSP (mTSP) uses multiple salesmen starting from a depot, modeling fleet routing. Each variant changes the feasibility landscape and often requires customizing the core algorithm with additional state or penalty terms.

Optimizations for scaling traveling salesman problem algorithms focus on reducing constant factors, improving lower bounds, and parallelizing search. For Held-Karp, optimizations include using only two rows of DP at a time when reconstruction is not needed, employing meet-in-the-middle, and using bitset representations with Numba or C extensions. For branch and bound, stronger lower bounds via Held-Karp relaxation or minimum 1-tree can prune more aggressively. For large-scale heuristics, techniques like k-d trees accelerate nearest neighbor queries from O(n²) to O(n log n), and candidate lists restrict 2-opt to consider only nearby cities, reducing per-iteration cost from O(n²) to O(n).

Advanced Improvement Strategies

Lin-Kernighan is a powerful variable-opt heuristic that generalizes 2-opt and 3-opt by dynamically deciding how many edges to swap in each move, often achieving near-optimal solutions for instances with thousands of cities. Ant Colony Optimization and Simulated Annealing provide metaheuristic frameworks that balance exploration and exploitation through pheromone trails or temperature schedules. Modern solvers like Concorde combine branch-and-cut with sophisticated cutting planes and have solved instances with over 85,000 cities to optimality, demonstrating that careful engineering can push exact methods far beyond theoretical worst-case limits.

7. Real-World Applications

Traveling salesman problem algorithms are deployed across a surprising breadth of domains, often in disguised forms where the "cities" are not geographic locations. In logistics and transportation, TSP directly models last-mile delivery, where a van must visit dozens of drop points and return to the depot with minimal fuel and time. Companies like UPS and Amazon solve variants with time windows, vehicle capacities, and traffic-aware asymmetric costs, using a combination of exact solvers for route clusters and heuristics for large fleets. Even small improvements of 1-2% translate to millions in annual savings at scale.

In manufacturing and hardware design, TSP appears in circuit board drilling and VLSI chip design. A drill must visit thousands of holes on a printed circuit board, and minimizing travel time directly increases throughput. Similarly, wiring in very-large-scale integration seeks to minimize total wire length while connecting components, which reduces to a Steiner TSP variant. Robotics and warehousing use TSP for pick-and-place operations, where a robotic arm or automated guided vehicle must collect items in a warehouse with minimal movement.

Beyond physical routing, TSP models sequencing problems in computing and biology. In data centers, disk head scheduling and file defragmentation can be cast as TSP to minimize seek time. In bioinformatics, DNA sequencing by hybridization reconstructs a genome from fragments where overlap costs define distances, and the shortest superstring problem is closely related to asymmetric TSP. Telescope scheduling, X-ray crystallography, and even the ordering of database query joins have been formulated as TSP instances, where the cost of transitioning between observations or join orders must be minimized.

Applications in Web Systems and Networks

While less obvious, traveling salesman problem algorithms influence web servers, databases, and networks. Content delivery networks optimize the order in which edge caches are refreshed, database query optimizers search for optimal join orderings that minimize intermediate result sizes, and network administrators plan fiber optic cable layouts that connect data centers with minimal trenching cost. In each case, the core challenge is finding a low-cost permutation under constraints, and TSP heuristics provide practical solutions where exhaustive search is impossible.

Even in software engineering workflows, TSP-like optimization arises. Automated test suite ordering seeks to detect faults early by prioritizing tests that cover diverse code paths, similar to maximizing distance covered early in a tour. Compiler optimization for instruction scheduling must order operations to minimize pipeline stalls, a problem that can be modeled as a variant of TSP on a dependency graph. Recognizing these isomorphisms allows engineers to reuse well-studied TSP solvers rather than developing bespoke optimizers.

8. Comparison with Alternatives

Choosing traveling salesman problem algorithms requires understanding how they relate to other graph algorithms that solve superficially similar problems. Unlike shortest path algorithms that find the cheapest route between two specific vertices, TSP must visit all vertices exactly once and return to the start, which imposes a global Hamiltonian constraint. Minimum spanning tree algorithms find the cheapest set of edges connecting all vertices without cycles, which is a relaxation of TSP and often used as a lower bound or building block.

Compared to Hamiltonian path algorithms that seek any cycle visiting all vertices without minimizing cost, TSP adds an optimization objective that dramatically increases difficulty. Euler tour algorithms, which traverse every edge exactly once, are polynomial-time solvable, whereas Hamiltonian cycle is NP-complete. This distinction highlights why TSP is hard: the constraint is on vertices, not edges, and the cost function couples all decisions globally.

Within TSP itself, the choice between exact, approximation, and heuristic methods depends on instance size, required optimality, and time budget. Exact methods are appropriate for n < 30 or when optimality is non-negotiable, such as in chip design verification. Approximation algorithms like Christofides are ideal for metric instances where a guaranteed bound is needed and n is moderate to large. Fast heuristics like nearest neighbor plus 2-opt are preferred for real-time systems with n in the hundreds or thousands where near-optimal is sufficient.

9. Common Mistakes and Best Practices

A frequent mistake when implementing traveling salesman problem algorithms is assuming Euclidean distances when the problem is actually asymmetric or non-metric. Using straight-line distance for a delivery route that must obey one-way streets or traffic patterns can produce tours that are infeasible or far from optimal in practice. Always validate the cost model against real-world constraints and consider whether the triangle inequality holds before applying approximations like Christofides that depend on it.

Another pitfall is neglecting to fix the starting city and accounting for tour rotations and reversals as distinct solutions. For symmetric TSP, each tour has 2n equivalent representations (n rotations times 2 directions), so enumerating all n! permutations wastes a factor of 2n work. Similarly, failing to use bitmask memoization correctly in Held-Karp leads to exponential recomputation. Ensure base cases are correctly initialized and that the DP table is sized as (1 << n) by n, which grows rapidly and can exhaust memory if n is underestimated.

Over-reliance on a single heuristic without local improvement is also common. Nearest neighbor alone can produce tours up to O(log n) times worse than optimal in the worst case. Best practice is to use a construction heuristic to seed a local search like 2-opt or 3-opt, and to run multiple restarts from different starting cities or random tours. For genetic algorithms, insufficient population diversity leads to premature convergence; maintain diversity through mutation and avoid overly aggressive elitism.

Best Practices for Production Use

For production systems, profile and benchmark on representative data rather than relying solely on asymptotic analysis. An O(n² * 2ⁿ) DP may outperform branch and bound for n=20 but fail for n=50 where a heuristic is required. Use established libraries such as OR-Tools, Concorde, or LKH for large instances instead of reimplementing from scratch, as they incorporate decades of optimizations including cutting planes and sophisticated data structures.

Implement robust input validation, handle disconnected graphs by assigning large costs to missing edges, and consider numerical stability when costs are floating point. Cache distance computations, use delta evaluation for local search to avoid O(n) recomputation per move, and parallelize independent restarts. Finally, document the chosen algorithm's guarantees and limitations clearly so downstream users understand whether they are receiving an optimal, approximated, or heuristic solution and can set expectations accordingly.

10. Interview Questions

Interview questions on traveling salesman problem algorithms test understanding of NP-hardness, dynamic programming, and the ability to trade optimality for efficiency. Below are common questions with guidance on what interviewers expect.

Q1: Why is TSP considered NP-hard and what does that imply for solving it?

Answer should explain that TSP's decision version (is there a tour with cost ≤ k?) is NP-complete via reduction from Hamiltonian Cycle, and its optimization version is NP-hard. This implies no known polynomial-time exact algorithm exists, and finding one would prove P = NP. In practice, it means we must use exponential exact algorithms for small n or polynomial heuristics/approximations for large n. Mention that verification of a tour is polynomial, which places the decision problem in NP.

Q2: Explain the Held-Karp DP recurrence and its complexity.

Expected answer: Define DP[mask][i] as minimum cost to start at 0, visit set mask, end at i. Recurrence DP[mask][i] = min_{j in mask, j != i} DP[mask ^ (1 << i)][j] + dist[j][i] with base DP[1][0]=0. Complexity is O(n² * 2ⁿ) time because there are O(n * 2ⁿ) states and each transition iterates over O(n) predecessors, and O(n * 2ⁿ) space. Discuss how bitmask represents subsets and why fixing start reduces state space. Bonus points for mentioning reconstruction via parent pointers.

Q3: How does Christofides' algorithm achieve a 1.5-approximation and when does it apply?

Answer should outline steps: compute MST, find minimum-weight perfect matching on odd-degree vertices, combine to form Eulerian multigraph, find Eulerian tour, shortcut to Hamiltonian cycle. Prove bound: MST ≤ OPT, matching ≤ OPT/2, so combined ≤ 1.5*OPT. Emphasize it applies only to metric TSP where triangle inequality holds and graph is symmetric and complete; otherwise shortcutting may increase cost and guarantee fails. Contrast with general TSP which has no constant-factor approximation unless P = NP.

Q4: Compare 2-opt with nearest neighbor. When would you use each?

Nearest neighbor is a construction heuristic that builds a tour greedily in O(n²) but has no guarantee and can be arbitrarily bad. 2-opt is an improvement heuristic that takes an existing tour and iteratively swaps two edges to reduce length until local optimum. In practice, use nearest neighbor to generate an initial tour quickly, then apply 2-opt or 3-opt to improve it. For interviews, discuss time per iteration O(n²), need for multiple restarts, and that 2-opt can get stuck in local optima, motivating Lin-Kernighan or simulated annealing.

Q5: How would you handle a TSP with 10,000 cities in a real-time delivery system?

Strong answer acknowledges exact methods are infeasible (2ⁿ impossible). Propose hierarchical approach: cluster cities geographically, solve clusters with heuristics, then merge. Use fast construction plus Lin-Kernighan or OR-Tools' guided local search, possibly with time limits. Mention techniques like candidate lists, parallel restarts, and incremental reoptimization when new orders arrive. Discuss trade-off between solution quality and latency, and suggest measuring gap to MST lower bound to estimate optimality. Also consider variant constraints like time windows and vehicle capacity, framing as Vehicle Routing Problem.