0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

コード

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 行目を変えれば単一始点になります。

おわり

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?