1.初めに
・アルゴリズムを学ぶために、競技プログラミングを始めました。
・AOJのコースをやっていくので、その備忘録を残します。
・前回は巨大ナップサック問題を解いたので、今回からは新たなトピックの「巡回セールスマン問題」を解いていきます。
2.巡回セールスマン問題
2.1問題
重み付き有向グラフ $G(V,E)$ について、以下の条件を満たす最短経路の距離を求めて下さい：
- ある頂点から出発し、出発点へ戻る閉路である。
- 各頂点をちょうど１度通る。
入力
$|V|$ , $|E|$ はそれぞれグラフ $G$ の頂点の数と辺の数を示す。グラフ $G$ の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられている。
$s_i$, $t_i$ はグラフ $G$ の $i$ 番目の辺が結ぶ２つの頂点を表す（有向）。$d_i$ は $s_i$ と $t_i$ の間の距離 （$i$ 番目の辺の重み）である。
出力
最短経路の距離を1行に出力する。条件を満たす経路がない場合は $-1$ と出力する。
制約
- $2 ≤ |V| ≤ 15$
- $0 ≤ d_i ≤ 1,000$
- $G$ に多重辺はない
3.グラフ
・そもそも有向グラフってなんですか？
↓
4.解き方
・下の入力例を元に考えていきます。
4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4
↓ つまり
|V|=4,|E|=6
\\
\\
s,t,d\\
0,1,2\\
1,2,3\\
1,3,9\\
2,0,1\\
2,3,6\\
3,2,4\\
(s:移動前の頂点、t:移動後の頂点、d:sからtまでの距離)
・これを図で書いてみます。
・ノード(頂点)やエッジ(矢印)が増えると図を描くのは大変なので、描かなくて大丈夫です。
4.1.隣接行列を作る
・「どの頂点とどの頂点が矢印で繋がっていて、どの方向に行くとどれくらいの距離がかかるのか」を行列Aとして表します。
i：移動前の頂点
j：移動後の頂点
として
$$
A[i][j]=頂点iから頂点jへ移動するときの距離
$$
としてAを埋めていきます。
・入力例では図を見ながら簡単に埋めることができます。(隣接していない部分の要素はinfで埋めます)
・例えば頂点$0$から頂点$1$へ行く時の距離は$2$なので、$A[0][1]=2$となります。
| i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | inf | 2 | inf | inf |
| 1 | inf | inf | 3 | 9 |
| 2 | 1 | inf | inf | 6 |
| 3 | inf | inf | 4 | inf |
4.2.DPテーブルを作る
・隣接行列とは別にdp表も作ります。
i：通らなければならない頂点(の集合)
j：最後に到達する頂点
※「最後に到達する頂点」は「通らなければならない頂点」に含まれてなければなりません。
※「開始の頂点0」は「通らなければならない頂点」に含まれていません。
として
$$
dp[i][j]=頂点0から出発し、i番目の頂点の集合にある全ての頂点を通り、jの頂点に終着する時の最短経路
$$
としてdp表を埋めていきます。
・ひとまず、dp表は以下↓のように書いてみたいと思います。(要素はinfで埋まっています)
| i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | inf | inf | inf | inf |
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| ･･･ | ･･･ | ･･･ | ･･･ | ･･･ |
・まず、「i：通らなければならない頂点(の集合)」とはなんなのかを考えます。
↓
・「{0}：頂点0を必ず通らなければならない」、「{2,3}：頂点2と頂点3を必ず通らなければならない」といった表し方をしていきます。
↓
・つまり、iは頂点の数のすべての組み合わせ($=4^2=16$)通りあります。
↓
・一般的には、iは頂点の数$V$のすべての組み合わせなので$V^2$通りあります。
↓
・それを加えるとdp表は以下↓のようになります。(※頂点の集合の順番はテキトーです)
| 頂点の集合 | i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|
| {∅} | 0 | inf | inf | inf | inf |
| {0} | 1 | ||||
| {1} | 2 | ||||
| {2} | 3 | ||||
| {3} | 4 | ||||
| {0,1} | 5 | ||||
| {0,2} | 6 | ||||
| {0,3} | 7 | ||||
| {1,2} | 8 | ||||
| {1,3} | 9 | ||||
| {2,3} | 10 | ||||
| {0,1,2} | 11 | ||||
| {0,1,3} | 12 | ||||
| {0,2,3} | 13 | ||||
| {1,2,3} | 14 | ||||
| {0,1,2,3} | 15 |
※{∅}：空集合(集合の中に要素が無い)：どの点も通らない
・つまり、上の表で言うとdp[8][3]は「頂点0から出発し、頂点1と頂点2を通って、頂点3に終着するときの最短経路」と言い換えられます。
ここで!!!!!!!!!
頂点の集合の順番を、ある法則で並び変えていきます!!!!!!!!
iを「ビット列」として考えて、頂点の集合と対応させていきます!!!←これがややこしい、、、
4.2.1.ビット列って何?
２進数
・ビット列を以下のように見て、頂点の集合と対応させていきます。
・例えば、i=9の時、ビット列(2進数)は「1001」なので、{0,3}、他にも例えばi=15の時、ビット列(2進数)は「1111」なので、{0,1,2,3}の頂点の集合に対応しています。
・これを元にdp表を作ると以下のようになります。
| iに対応した頂点の集合 | i(ビット列表記) | i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|---|
| {∅} | 0000 | 0 | inf | inf | inf | inf |
| {0} | 0001 | 1 | ||||
| {1} | 0010 | 2 | ||||
| {0,1} | 0011 | 3 | ||||
| {2} | 0100 | 4 | ||||
| {0,2} | 0101 | 5 | ||||
| {1,2} | 0110 | 6 | ||||
| {0,1,2} | 0111 | 7 | ||||
| {3} | 1000 | 8 | ||||
| {0,3} | 1001 | 9 | ||||
| {1,3} | 1010 | 10 | ||||
| {0,1,3} | 1011 | 11 | ||||
| {2,3} | 1100 | 12 | ||||
| {0,2,3} | 1101 | 13 | ||||
| {1,2,3} | 1110 | 14 | ||||
| {0,1,2,3} | 1111 | 15 |
・初期値$dp[0][0]$は「頂点0から出発し、どの頂点も通らず頂点0に終着する」、つまり「動かない」なので、$dp[0][0]=0$となります。
・一つ一つ考えていくとわかるように、エッジが有向なので、値が入る部分はほとんどありません。
・全て埋めてみると以下のようになります。
| i(ビット列表記) | i\j | 0 | 1 | 2 | 3 | |
|---|---|---|---|---|---|---|
| {∅} | 0000 | 0 | 0 | inf | inf | inf |
| {0} | 0001 | 1 | inf | inf | inf | inf |
| {1} | 0010 | 2 | inf | 2 | inf | inf |
| {0,1} | 0011 | 3 | inf | inf | inf | inf |
| {2} | 0100 | 4 | inf | inf | inf | inf |
| {0,2} | 0101 | 5 | inf | inf | inf | inf |
| {1,2} | 0110 | 6 | inf | inf | 5 | inf |
| {0,1,2} | 0111 | 7 | 7 | inf | inf | inf |
| {3} | 1000 | 8 | inf | inf | inf | inf |
| {0,3} | 1001 | 9 | inf | inf | inf | inf |
| {1,3} | 1010 | 10 | inf | inf | inf | 11 |
| {0,1,3} | 1011 | 11 | inf | inf | inf | inf |
| {2,3} | 1100 | 12 | inf | inf | inf | inf |
| {0,2,3} | 1101 | 13 | inf | inf | inf | inf |
| {1,2,3} | 1110 | 14 | inf | inf | 15 | 11 |
| {0,1,2,3} | 1111 | 15 | 16 | inf | inf | inf |
・例えばdp[6][2]の場合、「0から出発し、頂点{1,2}を通り2に終着するときの最短経路」なので$dp[6][2]=5$となります。(最後に到達する頂点(j)は、通らなければならない頂点の集合(i)に含まれています。)
・問題文は「各頂点をちょうど一度通る最短経路」なので言い換えると、「0から出発し、頂点{0,1,2,3}を通り0に終着するときの最短経路」であるので$dp[15][0]=16$が答えとなります。
・これを式で表すと、
dp[i][j1] = min(dp[i][j1],dp[i^{(1<<j1)}][j2] + A[j2][j1])\\
(j1:移動前の頂点、j2:移動後の頂点)
となります。
4.2.2. ビット列の演算
・上の式に出てくる「<<」の意味について説明します。
x<<y：xの桁をyだけ左にシフトし、空いたところに0を入れる。(xはビット列)
・例えば、「1<<3」の場合は、「1000=8」となります。
・「>>」と書かれている場合は、右にシフトします。
・例えば、「8>>3」の場合は、「0001=1」となります。
5.実装
# 入力値取得
V,E=map(int,input().split())
inf=float("inf")
# 隣接行列Aを作る
A=[[inf]*V for i in range(V)]
for i in range(E):
s,t,d=map(int,input().split())
A[s][t]=d
# dp表を作る
dp=[[inf]*V for i in range(2**V)]
# 初期値を入れる
dp[0][0]=0
# 空({∅})の時を除いた頂点集合で回す
for i in range(1,2**V):
# 移動後の頂点で回す
for j1 in range(V):
# 移動前の頂点で回す
for j2 in range(V):
# 「移動後の頂点が頂点集合に含まれている」かつ「移動後と移動前の頂点が同じでない」かつ「移動後と移動前の頂点が隣接している」かを判断
if i>>j1 & 1 and not j1==j2 and not A[j2][j1]==inf:
dp[i][j1] = min(dp[i][j1],dp[i^(1<<j1)][j2]+A[j2][j1])
if not dp[2**V-1][0]==inf:
print(dp[2**V-1][0])
# 条件を満たす経路がない場合
else:
print(-1)
5.1. if i>>j1 & 1 and not j1==j2 and not A[j2][j1]==inf:について
・dp[i][j1]に要素が入る条件として、「移動後の頂点が頂点集合に含まれている」かつ「移動後と移動前の頂点が同じでない」かつ「移動後と移動前の頂点が隣接している」かの三つの条件を判断しています。
5.1.1. if i>>j1 & 1:について
・このif文で「移動後の頂点(j1)が頂点集合iに含まれているかどうか」を判断できます。
・if i>>j1 & 1:は言い換えると、「iのj1桁目の数字(0か1)を取り出している」と言えます。
・つまり、「移動後の頂点j1が、iでは0か1のどちらであるかを判断している」と言えます。
・「移動後の頂点j1が、iでは1」ならば「j1は通らなければならに頂点酒豪に含まれている」と言えます。
