Data Structures Algorithms 简明教程
Travelling Salesman Problem (Dynamic Approach)
旅行商问题是最臭名昭著的计算问题。我们可以使用蛮力法来评估每种可能的路径并选择最佳的路径。对于图中的 n 个顶点来说，共有 (n−1)! 种可能性。因此，具有更高的复杂度。
然而，使用动态规划方法而不是使用蛮力法可以在更短的时间内获得解决方案，尽管没有多项式时间算法。
Travelling Salesman Dynamic Programming Algorithm
让我们考虑一个图 G = (V,E) ，其中 V 是城市集合，而 E 是加权边集合。边 e(u, v) 表示顶点 u 和 v 是相连的。顶点 u 和 v 之间的距离是 d(u, v) ，它应该是非负的。
假设我们已经从城市 1 开始，现在在访问了一些城市之后，我们来到了城市 j 。因此，这是一条部分路径。我们当然需要知道 j ，因为它将决定接下来访问哪些城市最方便。我们还需要知道到目前为止访问的所有城市，以便我们不会重复任何城市。因此，这是一个适当的子问题。
对于包含 1 的城市子集 S $\epsilon$ {1,2,3,…,n} ，其中 j $\epsilon$ S, let C(S, j) 为在 S 中访问每个结点一次的最短路径的长度，从 1 开始，在 j 结束。
当 |S|> 1 时，我们定义 𝑪C(S,1)= $\propto$，因为路径不能在 1 开始和结束。
现在，让我们用较小的子问题来表达 C(S, j) 。我们需要从 1 开始，在 j 结束。我们应该选择下一个城市，使得
C\left ( S,j \right )\, =\, min\, C\left ( S\, -\, \left\{j \right\},i \right )\, +\, d\left ( i,j \right )\: where\: i\: \epsilon \: S\: and\: i\neq j
Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
for all subsets S є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j є S and j ≠ 1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)Example
在以下示例中，我们将举例说明解决旅行商问题所采取的步骤。
根据以上图表，准备了下表。
S = $\Phi$
成本\left ( 2, \Phi, 1 \right )\,=\, d\left ( 2,1 \right )\,=\,5
成本\left ( 3, \Phi, 1 \right )\,=\, d\left ( 3,1 \right )\,=\,6
成本\left ( 4, \Phi, 1 \right )\,=\, d\left ( 4,1 \right )\,=\,8
S = 1
成本\left ( i, s \right )=\min\left\{成本\left ( j, s-(j) \right )\,+\,d\left [ i, j \right ] \right\}
成本\left ( 2, \left\{3 \right\}, 1 \right )=d\left[2,3 \right ]\,\,成本\left ( 3, \Phi, 1 \right )\,=\,9\,\,6\,=\,15
成本\left ( 2, \left\{4 \right\}, 1 \right )=d\left[2,4 \right ]\,\,成本\left ( 4, \Phi, 1 \right )\,=\,10\,\,8\,=\,18
成本\left ( 3, \left\{2 \right\}, 1 \right )=d\left[3,2 \right ]\,\,成本\left ( 2, \Phi, 1 \right )\,=\,13\,\,5\,=\,18
成本\left ( 3, \left\{4 \right\}, 1 \right )=d\left[3,4 \right ]\,\,成本\left ( 4, \Phi, 1 \right )\,=\,12\,\,8\,=\,20
成本\left ( 4, \left\{3 \right\}, 1 \right )=d\left[4,3 \right ]\,\,成本\left ( 3, \Phi, 1 \right )\,=\,9\,\,6\,=\,15
成本\left ( 4, \left\{2 \right\}, 1 \right )=d\left[4,2 \right ]\,\,成本\left ( 2, \Phi, 1 \right )\,=\,8\,\,5\,=\,13
S = 2
成本\left ( 2, \left\{3,4 \right\}, 1 \right )=\min\left\{\begin{matrix}d\left [ 2,3 \right ]\,\,成本\left ( 3, \left\{4\right\}, 1 \right )\,=\,9\,\,20\,=\,29 \\ d\left [ 2,4 \right ]\,\,成本\left ( 4, \left\{3\right\}, 1 \right )\,=\,10\,\,15\,=\,25 \\ \end{matrix}\right.\,=\,25
成本\left ( 3, \left\{2,4 \right\}, 1 \right )=\min\left\{\begin{matrix}d\left [ 3,2 \right ]\,\,成本\left ( 2, \left\{4\right\}, 1 \right )\,=\,13\,\,18\,=\,31 \\ d\left [ 3,4 \right ]\,\,成本\left ( 4, \left\{2\right\}, 1 \right )\,=\,12\,\,13\,=\,25 \\ \end{matrix}\right.\,=\,25
成本\left ( 4, \left\{2,3 \right\}, 1 \right )=\min\left\{\begin{matrix}d\left [ 4,2 \right ]\,\,成本\left ( 2, \left\{3\right\}, 1 \right )\,=\,8\,\,15\,=\,23 \\ d\left [ 4,3 \right ]\,\,成本\left ( 3, \left\{2\right\}, 1 \right )\,=\,9\,\,18\,=\,27 \\ \end{matrix}\right.\,=\,23
S = 3
成本\left ( 1, \left\{2,3,4 \right\}, 1 \right )=\min\left\{\begin{matrix}d\left [ 1,2 \right ]\,\,成本\left ( 2, \left\{3,4\right\}, 1 \right )\,=\,10\,\,25\,=\,35 \\ d\left [ 1,3 \right ]\,\,成本\left ( 3, \left\{2,4\right\}, 1 \right )\,=\,15\,\,25\,=\,40 \\ d\left [ 1,4 \right ]\,\,成本\left ( 4, \left\{2,3\right\}, 1 \right )\,=\,20\,\,23\,=\,43 \\ \end{matrix}\right.\,=\,35
最小成本路径为 35。
从成本 {1, {2, 3, 4}, 1} 开始，可得到 d[1, 2] 的最小值。当 s = 3 时，选择从 1 到 2 的路径（成本为 10），然后反向移动。当 s = 2 时，可得到 d[4, 2] 的最小值。选择从 2 到 4 的路径（成本为 10），然后反向移动。
当 s = 1 时，可得到 d[4, 2] 的最小值，但 2 和 4 已被选中。因此，我们选择 d[4, 3]（d[2, 3] 和 d[4, 3] 的两个可能值分别为 15，但路径的最后一个节点是 4）。选择路径 4 到 3（成本为 9），然后进入 s = ϕ 步骤。可得到 d[3, 1] 的最小值（成本为 6）。
