5.4 旅行銷售員與漢米爾頓迴路#

from itertools import permutations

def tsp_brute_force(dist):
    """暴力法：O(n!)"""
    n = len(dist)
    best, best_path = float('inf'), None
    for perm in permutations(range(1, n)):
        path = (0,) + perm + (0,)
        length = sum(dist[path[i]][path[i + 1]]
                     for i in range(n))
        if length < best:
            best, best_path = length, path
    return best, best_path

def tsp_held_karp(dist):
    """Held-Karp 動態規劃：O(n^2 * 2^n)"""
    n = len(dist)
    FULL = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]
    dp[1][0] = 0                      # 起點 0 已拜訪
    for S in range(1 << n):
        for j in range(n):
            if not (S >> j) & 1 or dp[S][j] == float('inf'):
                continue
            for k in range(n):
                if (S >> k) & 1:
                    continue
                ns = S | (1 << k)
                cand = dp[S][j] + dist[j][k]
                if cand < dp[ns][k]:
                    dp[ns][k] = cand
                    parent[ns][k] = j
    # 回到起點並回溯路徑
    best, last = min((dp[FULL][j] + dist[j][0], j)
                     for j in range(1, n))
    path, j = [], last
    for _ in range(n - 1):
        path.append(j)
        j = parent[FULL][j]
        # 注意：回溯需配合遮罩縮小，此處示範略
    return best

import math
pts = [(0, 0), (2, 3), (5, 1), (6, 4), (1, 5)]
d = [[math.dist(a, b) for b in pts] for a in pts]
print(tsp_brute_force(d))
print(tsp_held_karp(d))