ここでは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)]
＃１行の要素数がｎ個ある、つまりｎ行あるリスト＝１次元配列を作成しえそれぞれを０で初期化。入力例の場合は４個
★for i in range(n):
a[i] = list(map(int, input().split()))
＃各行にそれぞれの都市から別な年に移るコストを記した数値の文字列を４行分読んで数値にsplit()で区切ってmap()でint=整数にして格納。
これで、a[i]はa[i][j]といった２次元配列になった。
※この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乗と非常に大きな数にして、初期化しました。
例えば入力例１では都市は４個。なので、各都市について、自分も含め、残り3都市全部訪問したら２進数で1111 まったく訪問してない状態は0000
年４と都市１を訪問したら 1001。
必要な訪問のパターン数は２進数の各桁は０か１の２通りなので、4つの歳２の8乗通り分の数が必要となる。
各行に４つの要素がある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進数に直すと０から257とないますね。
だからfor j in range(1 << n):は258回繰り返します。
＃次にfor i in range(n):で、iは今たたどり着いている場所ですね。
都市1の０から３まで変わりますね。
次に for k in range(n):です。
今、iが最初の0でした。
０にたどり着くのは0から含めて、１，２，３とあります。
だからkは直前に居た年を表すので0から3まで変化します。
そこで、一つ前の状態は都市ｋまでの最小コストであるdp[k][j]に
都市kからiに渡るためのコストa[i][j]を足したものですので、
dp[i][j]+a[i][j]となりますね。
ところが、jにはkすでに訪問した記録であるjの数がある。
年ｋをあわわす二進数は２のk乗である。
例 kが都市２の場合 kの２進数での場所は都市は0,1,2,3なので
2の2乗で4。これをｊから引けばkの訪問記録をあわわす
2進数の１を引くことになる。
例えば都市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が４ならjの最大値は二進数で1111。10進数で257
i=0に戻ってきた。jが257になるまで調べた。
それで、この値を表示すれば良い。
という事ですね。
