TSP: Brute Force, Backtracking & Sorted Edges

A Bit of History

Before Michael Held and Richard Karp's 1962 dynamic-programming breakthrough (covered in its own deep dive), the earliest computational attacks on TSP were purely combinatorial. Brute-force permutation search is the mathematically obvious baseline every TSP researcher starts from — it requires no cleverness, only patience (and a very fast computer, or a very small city count). The Sorted Edges method (also called Cheapest Link) emerged from operations research practice in the 1970s as a simple greedy alternative to Nearest Neighbor, building the tour by edges rather than by city-visitation order — a subtly different greedy philosophy that sometimes avoids Nearest Neighbor's worst pitfalls.

TSP Brute Force: Permutation Enumeration

Fix a starting city (WLOG, since a tour is a cycle), then enumerate every permutation of the remaining $n-1$ cities, compute each permutation's total tour cost, and keep the cheapest. This guarantees the true optimal tour, at the cost of $O((n-1)!)$ time.

TSP Backtracking: Bounding & Pruning

Rather than generating every full permutation before evaluating it, backtracking builds a partial tour incrementally and abandons a branch the moment its partial cost already exceeds the best complete tour found so far (branch-and-bound pruning):

• Maintain a running "best known tour cost" (initialized to $\infty$, or a quick heuristic solution like Nearest Neighbor).
• Build the tour city by city; after adding each city, check if the partial cost already exceeds the best known — if so, prune this branch immediately (no permutation extending it can possibly improve on the best).
• Whenever a complete tour is found with a cost better than the current best, update the best known cost.

Sorted Edges (Cheapest Link)

Instead of building a tour by choosing the next city to visit (as Nearest Neighbor does), Sorted Edges builds a tour by choosing the cheapest available edges across the entire graph, subject to two constraints that keep the growing edge set a valid partial tour:

• Sort all edges by ascending weight.
• Process edges in that order; add an edge to the tour if and only if (a) neither endpoint already has degree 2 (a valid tour visits each city exactly once, meaning exactly 2 tour-edges per city), and (b) adding it would not close a cycle smaller than the full $n$-city tour (a "premature subtour").
• Continue until exactly $n$ edges have been selected, forming one single Hamiltonian cycle.

Worked Example

4-city symmetric TSP with distances: AB=10, AC=15, AD=20, BC=35, BD=25, CD=30.

• Sorted edges (ascending): AB(10), AC(15), BD(25), CD(30), BC(35), AD(20) — wait, sort correctly: AB(10), AC(15), AD(20), BD(25), CD(30), BC(35).
• Add AB(10): degrees A=1, B=1. Add AC(15): degree A becomes 2 (max reached) — but wait, this would make A's degree 2 while B and C both still need one more edge. Add AD(20): A already has degree 2 (from AB, AC) — skip, would exceed degree 2. Add BD(25): degrees B=2, D=1. Add CD(30): degrees C=2, D=2 — completes the tour with exactly 4 edges: AB, AC, BD, CD, forming cycle A-B-D-C-A. Total cost: 10+25+30+15 = 80.

Complexity Analysis

Implementation

from itertools import permutations

def tsp_brute_force(dist, n):
    """Exact TSP via full permutation enumeration. dist: n x n matrix."""
    best_cost = float('inf')
    best_tour = None
    cities = list(range(1, n))  # fix city 0 as start

    for perm in permutations(cities):
        tour = [0] + list(perm)
        cost = sum(dist[tour[i]][tour[i+1]] for i in range(n - 1)) + dist[tour[-1]][0]
        if cost < best_cost:
            best_cost = cost
            best_tour = tour

    return best_tour, best_cost

def tsp_backtracking(dist, n):
    """Branch-and-bound backtracking TSP."""
    best = [float('inf'), None]
    path = [0]
    visited = [False] * n
    visited[0] = True

    def backtrack(cost_so_far):
        if cost_so_far >= best[0]:
            return  # prune: already worse than best known
        if len(path) == n:
            total = cost_so_far + dist[path[-1]][0]
            if total < best[0]:
                best[0] = total
                best[1] = path[:]
            return

        for city in range(n):
            if not visited[city]:
                visited[city] = True
                path.append(city)
                backtrack(cost_so_far + dist[path[-2]][city])
                path.pop()
                visited[city] = False

    backtrack(0)
    return best[1], best[0]

def sorted_edges_tsp(dist, n):
    """Sorted Edges (Cheapest Link) constructive heuristic."""
    edges = [(dist[i][j], i, j) for i in range(n) for j in range(i+1, n)]
    edges.sort()

    degree = [0] * n
    parent = list(range(n))  # union-find for subtour detection

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    tour_edges = []
    for w, u, v in edges:
        if len(tour_edges) == n:
            break
        if degree[u] < 2 and degree[v] < 2:
            ru, rv = find(u), find(v)
            # Allow closing the cycle only on the very last edge
            if ru != rv or len(tour_edges) == n - 1:
                tour_edges.append((u, v, w))
                degree[u] += 1
                degree[v] += 1
                parent[ru] = rv

    total_cost = sum(w for _, _, w in tour_edges)
    return tour_edges, total_cost

# Example: 4 cities
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
n = 4

print("Brute force:", tsp_brute_force(dist, n))
print("Backtracking:", tsp_backtracking(dist, n))
print("Sorted Edges:", sorted_edges_tsp(dist, n))

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int find(vector<int>& parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}

vector<pair<int,int>> sortedEdgesTSP(vector<vector<int>>& dist, int n, int& totalCost) {
    vector<tuple<int,int,int>> edges;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edges.push_back({dist[i][j], i, j});
    sort(edges.begin(), edges.end());

    vector<int> degree(n, 0);
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);

    vector<pair<int,int>> tourEdges;
    totalCost = 0;

    for (auto& [w, u, v] : edges) {
        if ((int)tourEdges.size() == n) break;
        if (degree[u] < 2 && degree[v] < 2) {
            int ru = find(parent, u), rv = find(parent, v);
            if (ru != rv || (int)tourEdges.size() == n - 1) {
                tourEdges.push_back({u, v});
                degree[u]++; degree[v]++;
                parent[ru] = rv;
                totalCost += w;
            }
        }
    }
    return tourEdges;
}

int main() {
    int n = 4;
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    int totalCost = 0;
    auto tour = sortedEdgesTSP(dist, n, totalCost);

    cout << "Sorted Edges tour: ";
    for (auto& [u, v] : tour) cout << "(" << u << "-" << v << ") ";
    cout << "\nTotal cost: " << totalCost << endl;
    return 0;
}

import java.util.*;

public class TSPExactConstructive {
    static int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    public static List<int[]> sortedEdgesTSP(int[][] dist, int n) {
        List<int[]> edges = new ArrayList<>(); // {weight, u, v}
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist[i][j], i, j});
        edges.sort((a, b) -> a[0] - b[0]);

        int[] degree = new int[n];
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        List<int[]> tourEdges = new ArrayList<>();

        for (int[] e : edges) {
            int w = e[0], u = e[1], v = e[2];
            if (tourEdges.size() == n) break;
            if (degree[u] < 2 && degree[v] < 2) {
                int ru = find(parent, u), rv = find(parent, v);
                if (ru != rv || tourEdges.size() == n - 1) {
                    tourEdges.add(new int[]{u, v, w});
                    degree[u]++; degree[v]++;
                    parent[ru] = rv;
                }
            }
        }
        return tourEdges;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        List<int[]> tour = sortedEdgesTSP(dist, n);
        int total = 0;
        System.out.print("Sorted Edges tour: ");
        for (int[] e : tour) {
            System.out.print("(" + e[0] + "-" + e[1] + ") ");
            total += e[2];
        }
        System.out.println("\nTotal cost: " + total);
    }
}

Real-World Applications

Exercises

1. Solve a 6-city symmetric TSP instance using brute force and compare its runtime to backtracking with pruning.
2. Explain why Sorted Edges must check for "premature subtours" — construct an example where naively adding cheap edges would create a small cycle before all cities are included.
3. Compare the tour quality of Sorted Edges versus Nearest Neighbor on the same 6-city instance.
4. Challenge: Combine Sorted Edges with a subsequent 2-opt refinement pass and measure the improvement over Sorted Edges alone.

Limitations