TSP: Brute Force, Backtracking & Sorted Edges

from itertools import permutations
from math import isfinite


def validate_symmetric_tsp(dist):
    n = len(dist)
    if n < 3:
        raise ValueError("this simple-cycle implementation needs at least 3 cities")
    if any(len(row) != n for row in dist):
        raise ValueError("distance matrix must be square")
    for i in range(n):
        if dist[i][i] != 0:
            raise ValueError("diagonal distances must be zero")
        for j in range(i + 1, n):
            if not isfinite(dist[i][j]) or dist[i][j] < 0:
                raise ValueError("distances must be finite and nonnegative")
            if dist[i][j] != dist[j][i]:
                raise ValueError("distance matrix must be symmetric")
    return n


def tour_cost(dist, tour):
    return sum(dist[tour[i]][tour[i + 1]] for i in range(len(tour) - 1))


def tsp_brute_force(dist):
    """Exact enumeration with rotational and reversal symmetry removed."""
    n = validate_symmetric_tsp(dist)
    best_tour, best_cost = None, float("inf")

    for middle in permutations(range(1, n)):
        if middle[0] > middle[-1]:
            continue  # keep one orientation of each symmetric cycle
        tour = (0,) + middle + (0,)
        cost = tour_cost(dist, tour)
        if cost < best_cost:
            best_tour, best_cost = list(tour), cost
    return best_tour, best_cost


def sorted_edges_tsp(dist):
    """Return (ordered_tour, cost, selected_edges) using Cheapest Link."""
    n = validate_symmetric_tsp(dist)
    edges = sorted((dist[u][v], u, v) for u in range(n) for v in range(u + 1, n))
    parent, rank, degree = list(range(n)), [0] * n, [0] * n
    selected = []

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

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1

    for weight, u, v in edges:
        if degree[u] == 2 or degree[v] == 2:
            continue
        final_edge = len(selected) == n - 1
        if find(u) == find(v) and not final_edge:
            continue
        selected.append((u, v, weight))
        degree[u] += 1
        degree[v] += 1
        union(u, v)
        if len(selected) == n:
            break

    if len(selected) != n or any(d != 2 for d in degree):
        raise RuntimeError("failed to construct a Hamiltonian cycle")

    neighbors = [[] for _ in range(n)]
    for u, v, _ in selected:
        neighbors[u].append(v)
        neighbors[v].append(u)
    tour, previous, current = [0], -1, 0
    while True:
        a, b = neighbors[current]
        nxt = a if a != previous else b
        if nxt == 0:
            break
        tour.append(nxt)
        previous, current = current, nxt
    tour.append(0)
    return tour, tour_cost(dist, tour), selected


def tsp_backtracking(dist):
    """Exact branch-and-bound using an MST-based completion lower bound."""
    n = validate_symmetric_tsp(dist)
    seed_tour, seed_cost, _ = sorted_edges_tsp(dist)
    best_tour, best_cost = seed_tour, seed_cost
    path, visited = [0], [False] * n
    visited[0] = True

    def mst_cost(vertices):
        if len(vertices) < 2:
            return 0
        remaining = set(vertices)
        root = remaining.pop()
        cheapest = {v: dist[root][v] for v in remaining}
        total = 0
        while remaining:
            v = min(remaining, key=cheapest.get)
            total += cheapest[v]
            remaining.remove(v)
            for w in remaining:
                cheapest[w] = min(cheapest[w], dist[v][w])
        return total

    def search(cost_so_far):
        nonlocal best_tour, best_cost
        remaining = [v for v in range(1, n) if not visited[v]]
        if not remaining:
            total = cost_so_far + dist[path[-1]][0]
            if total < best_cost:
                best_cost, best_tour = total, path[:] + [0]
            return

        lower_bound = (cost_so_far
                       + min(dist[path[-1]][v] for v in remaining)
                       + mst_cost(remaining)
                       + min(dist[v][0] for v in remaining))
        if lower_bound >= best_cost:
            return

        for city in sorted(remaining, key=lambda v: dist[path[-1]][v]):
            visited[city] = True
            path.append(city)
            search(cost_so_far + dist[path[-2]][city])
            path.pop()
            visited[city] = False

    search(0)
    return best_tour, best_cost


distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print("Brute force:", tsp_brute_force(distances))
print("Backtracking:", tsp_backtracking(distances))
print("Cheapest Link:", sorted_edges_tsp(distances)[:2])