T04124:海贼王之伟大航路

tsp, http://cs101.openjudge.cn/practice/04124/

“我是要成为海贼王的男人！”，路飞一边喊着这样的口号，一边和他的伙伴们一起踏上了伟大航路的艰险历程。

路飞他们伟大航路行程的起点是罗格镇，终点是拉夫德鲁（那里藏匿着“唯一的大秘宝”——ONE PIECE）。而航程中间，则是各式各样的岛屿。

因为伟大航路上的气候十分异常，所以来往任意两个岛屿之间的时间差别很大，从A岛到B岛可能需要1天，而从B岛到A岛则可能需要1年。当然，任意两个岛之间的航行时间虽然差别很大，但都是已知的。

现在假设路飞一行从罗格镇（起点）出发，遍历伟大航路中间所有的岛屿（但是已经经过的岛屿不能再次经过），最后到达拉夫德鲁（终点）。假设他们在岛上不作任何的停留，请问，他们最少需要花费多少时间才能到达终点？

输入

输入数据包含多行。第一行包含一个整数N(2 < N ≤ 16)，代表伟大航路上一共有N个岛屿（包含起点的罗格镇和终点的拉夫德鲁）。其中，起点的编号为1，终点的编号为N。之后的N行每一行包含N个整数，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个岛屿出发到第j个岛屿需要的时间t(0 < t < 10000)。第i行第i个整数为0。

输出

输出为一个整数，代表路飞一行从起点遍历所有中间岛屿（不重复）之后到达终点所需要的最少的时间。

样例输入

样例输入1：
4
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0

样例输入2：
5
0 18 13 98 8
89 0 45 78 43 
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0

样例输出

样例输出1：
100

样例输出2：
137

提示

提示：对于样例输入1：路飞选择从起点岛屿1出发，依次经过岛屿3，岛屿2，最后到达终点岛屿4。花费时间为20+50+30=100。对于样例输入2：可能的路径及总时间为： 1,2,3,4,5: 18+45+96+52=211 1,2,4,3,5: 18+78+29+12=137 1,3,2,4,5: 13+38+78+52=181 1,3,4,2,5: 13+96+19+43=171 1,4,2,3,5: 98+19+45+12=174 1,4,3,2,5: 98+29+38+43=208 所以最短的时间花费为137 单纯的枚举在N=16时需要14!次运算，一定会超时。

这道题是一个典型的 旅行商问题 (TSP) —— 要求从起点（岛屿 1）出发，经过所有中间岛屿（每个只走一次），最终到达终点（岛屿 N），求最小花费。

起点固定为 1；终点固定为 N；中间点必须都经过；图是有向带权图。

N ≤ 16，显然不能枚举所有排列 (14! ≈ 8.7e10)。用 状态压缩 DP，复杂度 O(N·2^N)，N=16 时大约 16 * 2^16 ≈ 1M，完全可行。

备注：有时人们会口头说“O(N·2^N)”来表示“每个状态只处理 O(N) 的转移”，但更严格的写法应是 $O (N^{2} \cdot 2^{N})$ （因为总的状态数是 $N \cdot 2^{N}$ ，而每个状态又可能花 O(N) 转移）。为了避免歧义，建议用 $O (N^{2} \cdot 2^{N})$ 。

思路：TSP 的经典解法——Held–Karp 动态规划算法

设 dp[mask][i] = 从起点 1 出发，经过集合 mask 中的所有点，最后停在 i 点的最小花费。

mask 用二进制表示，mask 的第 j 位为 1 表示 j 已经访问过。
初始状态：dp[1<<0][0] = 0 （起点是 0 号点，即岛屿 1）。

状态转移：

dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j],
                           dp[mask][i] + cost[i][j])

其中 j 是还没访问过的新点。

最终答案是：

dp[(1<<N)-1][N-1]

表示所有点都访问过，最后停在终点 N-1。

Python实现

python

import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    cost = [[int(next(it)) for _ in range(N)] for _ in range(N)]

    INF = 10**12
    # dp[mask][i]: 已访问mask，最后在i的最小花费
    dp = [[INF] * N for _ in range(1 << N)]
    dp[1][0] = 0  # 起点(编号0)

    for mask in range(1 << N):
        for i in range(N):
            if dp[mask][i] == INF:
                continue
            for j in range(N):
                if mask >> j & 1:  # j 已经访问过
                    continue
                new_mask = mask | (1 << j)
                dp[new_mask][j] = min(dp[new_mask][j],
                                      dp[mask][i] + cost[i][j])

    print(dp[(1 << N) - 1][N - 1])

if __name__ == "__main__":
    solve()

T04124:海贼王之伟大航路 ​

T04124:海贼王之伟大航路