競プロ初中級者100問

DPL2A 巡回セールスマン問題

この記事で使うアルゴリズム

動的計画法
深さ優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja

この問題は動的計画法で解くことができます。

方針

全探索の計算量はO(N!)となり間に合いません。そこで動的計画法を用います。

経路は全ての頂点を通るため、頂点0からそれ以外の全ての頂点を通ったのち、頂点0に戻るというように考えて問題ありません。

集合Sに訪問済みで頂点vにいるとした時の頂点0まで戻るパスを考え、その経路長をdp[S][v]として計算します。ここでSが集合を表すため、実装上の工夫としてSを長さVのビット列として考えます（1は訪問済み、0は未訪問とします）。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
V, E = map(int, input().split())
INF = 10**10
cost = [[INF]*V for _ in range(V)] # 重み
for e in range(E):
    s, t, d = map(int,input().split())
    cost[s][t] = d

dp = [[-1] * V for _ in range(1<<V)] # dp[S][v]

def dfs(S, v, dp):
    if dp[S][v] != -1: # 訪問済みならメモを返す
        return dp[S][v]
    if S==(1<<V)-1 and v==0: # 全ての頂点を訪れて頂点0に戻ってきた
        return 0 # もう動く必要はない

    res = INF
    for u in range(V):
        if S>>u & 1 == 0: # 未訪問かどうか
            res = min(res, dfs(S|1<<u, u, dp)+cost[v][u])
    dp[S][v] = res
    return res

ans = dfs(0, 0, dp) # 頂点0からスタートする。ただし頂点0は未訪問とする
if ans == INF:
    print(-1)
else:
    print (ans)

参考

アルゴリズムの多くはプログラミングコンテストチャレンジブック(通称、アリ本)のP173-175を参考にさせていただきました。

記事情報

  • 投稿日：2020年5月21日
  • 最終更新日：2020年5月21日