bit DP（巡回セールスマン）

「どの頂点を訪れたか」を整数のビットで表し、集合と現在地を状態にした DP をします。 $N$ は 16 程度までが目安です。

• tsp(d, start): 距離行列 d（d[u][v] が $u$ から $v$ へのコスト）と出発点（既定は $0$）から、dp[S][v]（start から出発して集合 $S$ の頂点をすべて訪れ、いま $v$ にいるときの最小コスト）の表を返す。 $O(2^N N^2)$

使い方:

• 出発点に戻ってくる巡回路の最小コスト: min(dp[-1][v] + d[v][start] for v in range(n))
• 戻らずに全頂点を回る最小コスト: min(dp[-1])

辺がない組は、d に十分大きい値を入れておきます。

コード

def tsp(d, start=0):
    # dp[S][v] = start から出発して集合 S の頂点をすべて訪れ、いま v にいるときの最小コスト
    n = len(d)
    INF = 1 << 60
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1 << start][start] = 0
    for S in range(1 << n):
        dpS = dp[S]
        for v in range(n):
            if dpS[v] == INF:
                continue
            dv = d[v]
            for to in range(n):
                if S >> to & 1:
                    continue
                nd = dpS[v] + dv[to]
                if nd < dp[S | 1 << to][to]:
                    dp[S | 1 << to][to] = nd
    return dp