【競技プログラミング】巡回セールスマン問題をやってみた【組合せ最適化】

# 1.初めに
・アルゴリズムを学ぶために、競技プログラミングを始めました。
・AOJのコースをやっていくので、その備忘録を残します。

https://qiita.com/kindamu24005/private/cc0cb1e2498ca7f0dad0

・前回は巨大ナップサック問題を解いたので、今回からは**新たなトピック**の<B>「巡回セールスマン問題」</B>を解いていきます。

# 2.巡回セールスマン問題

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/2/DPL_2_A

## 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.グラフ
・そもそも**有向グラフ**ってなんですか？
　　　　　　↓
![巡回セールスマン.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/c6926972-ee76-24ec-ff77-0111087aae35.jpeg)


# 4.解き方
・下の入力例を元に考えていきます。
```
4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4
```
　　　　　　 　　　　　　 　　　　　　　　　 ↓　つまり
```math
|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までの距離)
```

・これを図で書いてみます。
![巡回セールスマン.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/6ffedf91-e020-dd49-5539-0b9280918a8c.jpeg)


・ノード(頂点)やエッジ(矢印)が増えると図を描くのは大変なので、描かなくて大丈夫です。

## 4.1.隣接行列を作る
・<B>「どの頂点とどの頂点が矢印で繋がっていて、どの方向に行くとどれくらいの距離がかかるのか」</B>を<B>行列A</B>として表します。

:::note
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表も作ります。

:::note
i：通らなければならない頂点(の集合)
j：最後に到達する頂点
<B>※「最後に到達する頂点」は「通らなければならない頂点」に含まれてなければなりません。
※「開始の頂点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**  |  |  |  |  |
|･･･  |･･･| ･･･ | ･･･ | ･･･ |

・まず、<B>「i：通らなければならない頂点(の集合)」</B>とはなんなのかを考えます。
　　　　　　↓
・<B>「{0}：頂点0を必ず通らなければならない」</B>、<B>「{2,3}：頂点2と頂点3を必ず通らなければならない」</B>といった表し方をしていきます。
　　　　　　↓
・つまり、<B>i</B>は頂点の数のすべての組み合わせ($=4^2=16$)通りあります。
　　　　　　↓
・一般的には、<B>i</B>は頂点の数$V$のすべての組み合わせなので$V^2$通りあります。
　　　　　　↓
・それを加えるとdp表は以下↓のようになります。<B>(※頂点の集合の順番はテキトーです)</B>

|頂点の集合|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**  |  |  |  |  |

<B>※{∅}：空集合(集合の中に要素が無い)：どの点も通らない</B>

・つまり、上の表で言うと<B>dp[8][3]</B>は<B>「頂点0から出発し、頂点1と頂点2を通って、頂点3に終着するときの最短経路」</B>と言い換えられます。

:::note warn
ここで!!!!!!!!!
頂点の集合の順番を、ある法則で並び変えていきます!!!!!!!!

**i**を<B>「ビット列」</B>として考えて、<B>頂点の集合と対応</B>させていきます!!!←これがややこしい、、、
:::

### 4.2.1.ビット列って何?
#### <font color="red"><B>２進数</B></font>



・ビット列を以下のように見て、頂点の集合と対応させていきます。
![巡回セールスマン.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/6cdabdfc-ddac-d0f1-e8fd-d76f7d2b8f1d.jpeg)

・例えば、<B>i=9</B>の時、ビット列(2進数)は<B>「1001」</B>なので、<B>{0,3}</B>、他にも例えば<B>i=15</B>の時、ビット列(2進数)は<B>「1111」</B>なので、<B>{0,1,2,3}</B>の頂点の集合に対応しています。

・これを元に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]$は<B>「頂点0から出発し、どの頂点も通らず頂点0に終着する」</B>、つまり<B>「動かない」</B>なので、$dp[0][0]=0$となります。

・一つ一つ考えていくとわかるように、<B>エッジが有向</B>なので、値が入る部分はほとんどありません。

・全て埋めてみると以下のようになります。

||i(ビット列表記)|i\j  |0  |1  |2  |3  |
|:---:|:---:|---|---|---|---|---|
|{∅}|0000|**0**  | <font color="red"><B>0 | inf | inf | inf |
|{0}|0001|**1**  | inf| inf | inf | inf |
|{1}|0010|**2**  | inf | <font color="red"><B>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 | <font color="red"><B>5 | inf |
|{0,1,2}|0111|**7**  | <font color="red"><B>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  | <font color="red"><B>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 | <font color="red"><B>15 | <font color="red"><B>11 |
|{0,1,2,3}|1111|**15**  | <font color="red"><B>16 | inf | inf | inf |

・例えば<B>dp[6][2]</B>の場合、<B>「0から出発し、頂点{1,2}を通り2に終着するときの最短経路」</B>なので$dp[6][2]=5$となります。<B>(最後に到達する頂点(j)は、通らなければならない頂点の集合(i)に含まれています。)</B>
![巡回セールスマン.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/e14a4436-7550-9a22-fc22-72694da9c6d5.jpeg)

・問題文は<B>「各頂点をちょうど一度通る最短経路」</B>なので言い換えると、<B>「0から出発し、頂点{0,1,2,3}を通り0に終着するときの最短経路」</B>であるので$dp[15][0]=16$が答えとなります。

・これを式で表すと、

```math
dp[i][j1] = min(dp[i][j1],dp[i^{(1<<j1)}][j2] + A[j2][j1])\\
(j1:移動前の頂点、j2:移動後の頂点)
```

となります。

### 4.2.2. ビット列の演算

・上の式に出てくる「<<」の意味について説明します。

:::note
x<<y：xの桁をyだけ左にシフトし、空いたところに0を入れる。(xはビット列)
:::

・例えば、「1<<3」の場合は、「1000=8」となります。

![巡回セールスマン.005.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/ce1050d9-1862-0763-9ac2-2f75c020f7aa.jpeg)

・「>>」と書かれている場合は、右にシフトします。

・例えば、「8>>3」の場合は、「0001=1」となります。

# 5.実装

```python
# 入力値取得
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]に要素が入る条件として、<B>「移動後の頂点が頂点集合に含まれている」かつ「移動後と移動前の頂点が同じでない」かつ「移動後と移動前の頂点が隣接している」</B>かの三つの条件を判断しています。

### 5.1.1. if i>>j1 & 1:について
・このif文で<B>「移動後の頂点(j1)が頂点集合iに含まれているかどうか」を判断できます。</B>

・<B>if i>>j1 & 1:</B>は言い換えると、<B>「iのj1桁目の数字(0か1)を取り出している」</B>と言えます。

・つまり、<B>「移動後の頂点j1が、iでは0か1のどちらであるかを判断している」</B>と言えます。

・<B>「移動後の頂点j1が、iでは1」</B>ならば<B>「j1は通らなければならに頂点酒豪に含まれている」</B>と言えます。
![巡回セールスマン.006.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/32282b35-0b58-1a0f-222b-a83229a46fe0.jpeg)