競技用にチューンした巡回セールスマン問題解法です。
コード
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 行目を変えれば単一始点になります。
おわり
誰かに使わせるには不親切かも。。。