競技用にチューンした巡回セールスマン問題解法です。

コード

def TSPdp(n, d, inf):
  ln = 1 << n
  dp = [inf] * (ln * n)
  for k in range(n): dp[ln * k + (1 << k)] = 0
  for i in range(1, 1 << n):
    for x in range(n):
      t = i + x * ln
      j = 1
      for y in range(n):
        if i & j:
          j <<= 1
          continue
        tt = (i | j) + y * ln
        if dp[tt] > dp[t] + d[x * n + y]: dp[tt] = dp[t] + d[x * n + y]
        j <<= 1
  return dp

$n$ を頂点数、$d$ を距離行列、たどり着けない場所の値 (無限) を $inf$ とします。

$\mathcal{O}(2^nn^2)$ の時間計算量で計算する動的計画法を行います。
dp テーブルは二次元配列を flatten して一次元にすることで参照コストを減らしています。

最終的な dp 配列は、
$$dp_{i2^n+j} := 現在地が i であり、訪問した頂点集合がbit表現でjとして表されるときのこの時点での最適解$$

となります。

使い方

$n$, $d$, $inf$ を入力して、出力を解読してください。特に、
$$dp_{i2^n+2^n - 1} := 終了地点が i であり、全頂点訪問した際の最適解$$

となります。

これは多始点ですが 4 行目を変えれば単一始点になります。

おわり

誰かに使わせるには不親切かも。。。