JOI公式テキストp127『巡回セールスマン問題』模範解答プログラムを徹底解説!

ここではJOI公式テキストp127巡回セールスマン問題の公式テキストに掲載されている模範解答プログラムを完全に理解できる詳しく分かりやすい解説を載せています。

Python言語 模範解答プログラム

INF = 10 ** 18

n = int(input())

a = [[0] * n for i in range(n)]

for i in range(n):
  a[i] = list(map(int, input().split()))

dp = [[INF] * (1 << n) for i in range(n)]

dp[0][0] = 0
  for j in range(1 << n): for i in range(n):
    for k in range(n):
      if (j >> k) & 1 == 0:
        continue
dp[i][j] = min(dp[i][j], dp[k][j - (1 << k)] + a[k][i])
  print(dp[0][(1 << n) - 1])

詳しい解説です

★INF = 10 ** 18

#これは下でつくるメモ化配列の初期化のために、使用します。
#まだ、最小値が求まっていないよ。という印です。

n = int(input()) #都市数は何個か?

a = [[0] * n for i in range(n)]

#1行の要素数がn個ある、つまりn行あるリスト=1次元配列を作成しえそれぞれを0で初期化。入力例の場合は4個

★for i in range(n):
a[i] = list(map(int, input().split()))

#各行にそれぞれの都市から別な年に移るコストを記した数値の文字列を4行分読んで数値にsplit()で区切ってmap()でint=整数にして格納。
これで、a[i]はa[i][j]といった2次元配列になった。
※このlist()map()の働きはこのサイトに分かりやすく載っています。

リストの説明はこちらです。

★dp = [[INF] * (1 << n) for i in range(n)]

#dp[i][j]という、今i番目の年にいます。すでにjに訪問した都市の数値が入っています。
この時点でのコストの最大値を記憶するメモ化配列を作りました。

# (1 << n) は 2 の n 乗を表します。

最大値はいくらになるか?予想がつかないので、INF = 10 ** 18 10の18乗と非常に大きな数にして、初期化しました。

例えば入力例1では都市は4個。なので、各都市について、自分も含め、残り3都市全部訪問したら2進数で1111 まったく訪問してない状態は0000
年4と都市1を訪問したら 1001。

必要な訪問のパターン数は2進数の各桁は0か1の2通りなので、4つの歳2の8乗通り分の数が必要となる。

各行に4つの要素がある2次元配列=2次元リストが作られた。

★dp[0][0] = 0
for j in range(1 << n): for i in range(n): for k in range(n): if (j >> k) & 1 == 0:
continue
dp[i][j] = min(dp[i][j], dp[k][j - (1 << k)] + a[k][i])
print(dp[0][(1 << n) - 1])

●#ここから動的計画法を開始します。

for j in range(1 << n):

jは訪問した都市の記録、痕跡を表します。全然訪問していなかったら0000

全都市訪問したら2進数で1111,全然訪問していなかったら0000

これを10進数に直すと0から257とないますね。

だからfor j in range(1 << n):は258回繰り返します。

#次にfor i in range(n):で、iは今たたどり着いている場所ですね。

都市1の0から3まで変わりますね。

次に for k in range(n):です。

今、iが最初の0でした。

0にたどり着くのは0から含めて、1,2,3とあります。

だからkは直前に居た年を表すので0から3まで変化します。

そこで、一つ前の状態は都市kまでの最小コストであるdp[k][j]に

都市kからiに渡るためのコストa[i][j]を足したものですので、

dp[i][j]+a[i][j]となりますね。

ところが、jにはkすでに訪問した記録であるjの数がある。

年kをあわわす二進数は2のk乗である。

例 kが都市2の場合 kの2進数での場所は都市は0,1,2,3なので

2の2乗で4。これをjから引けばkの訪問記録をあわわす

2進数の1を引くことになる。

例えば都市0のみ訪問した時のJは0001(2)=1(10)

都市3と2と0を訪問したのなら1101(2)

都市2のみ訪問なら0100(2) 4(10進数で)

なので、1101という10進数で13から4=2の2乗を引けばよい。

◆最後の表示の文

print(dp[0][(1 << n) - 1])

nが4ならjの最大値は二進数で1111。10進数で257

i=0に戻ってきた。jが257になるまで調べた。

それで、この値を表示すれば良い。

という事ですね。