Data Structures Algorithms 简明教程
Travelling Salesman Problem (Dynamic Approach)
旅行商问题是最臭名昭著的计算问题。我们可以使用蛮力法来评估每种可能的路径并选择最佳的路径。对于图中的 n 个顶点来说，共有 (n−1)! 种可能性。因此，具有更高的复杂度。
Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n−1)! number of possibilities. Thus, maintaining a higher complexity.
然而，使用动态规划方法而不是使用蛮力法可以在更短的时间内获得解决方案，尽管没有多项式时间算法。
However, instead of using brute-force, using the dynamic programming approach will obtain the solution in lesser time, though there is no polynomial time algorithm.
Travelling Salesman Dynamic Programming Algorithm
让我们考虑一个图 G = (V,E) ，其中 V 是城市集合，而 E 是加权边集合。边 e(u, v) 表示顶点 u 和 v 是相连的。顶点 u 和 v 之间的距离是 d(u, v) ，它应该是非负的。
Let us consider a graph G = (V,E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.
假设我们已经从城市 1 开始，现在在访问了一些城市之后，我们来到了城市 j 。因此，这是一条部分路径。我们当然需要知道 j ，因为它将决定接下来访问哪些城市最方便。我们还需要知道到目前为止访问的所有城市，以便我们不会重复任何城市。因此，这是一个适当的子问题。
Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don’t repeat any of them. Hence, this is an appropriate sub-problem.
对于包含 1 的城市子集 S $\epsilon$ {1,2,3,…,n} ，其中 j $\epsilon$ S, let C(S, j) 为在 S 中访问每个结点一次的最短路径的长度，从 1 开始，在 j 结束。
For a subset of cities S $\epsilon$ {1,2,3,…,n} that includes 1, and j $\epsilon$ S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.
当 |S|> 1 时，我们定义 𝑪C(S,1)= $\propto$，因为路径不能在 1 开始和结束。
When |S|> 1 , we define 𝑪C(S,1)= $\propto$ since the path cannot start and end at 1.
现在，让我们用较小的子问题来表达 C(S, j) 。我们需要从 1 开始，在 j 结束。我们应该选择下一个城市，使得
Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that
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)Analysis
最多有 2n.n 个子问题，每个子问题都需要线性时间来解决。因此，总运行时间为 O(2n.n2) 。
There are at the most 2n.n sub-problems and each one takes linear time to solve. Therefore, the total running time is O(2n.n2).
Example
在以下示例中，我们将举例说明解决旅行商问题所采取的步骤。
In the following example, we will illustrate the steps to solve the travelling salesman problem.
根据以上图表，准备了下表。
From the above graph, the following table is prepared.
S = $\Phi$
S = $\Phi$
成本\left ( 2, \Phi, 1 \right )\,=\, d\left ( 2,1 \right )\,=\,5
Cost\left ( 2,\Phi ,1 \right )\, =\, d\left ( 2,1 \right )\,=\,5
成本\left ( 3, \Phi, 1 \right )\,=\, d\left ( 3,1 \right )\,=\,6
Cost\left ( 3,\Phi ,1 \right )\, =\, d\left ( 3,1 \right )\, =\, 6
成本\left ( 4, \Phi, 1 \right )\,=\, d\left ( 4,1 \right )\,=\,8
Cost\left ( 4,\Phi ,1 \right )\, =\, d\left ( 4,1 \right )\, =\, 8
S = 1
S = 1
成本\left ( i, s \right )=\min\left\{成本\left ( j, s-(j) \right )\,+\,d\left [ i, j \right ] \right\}
Cost(i,s)=min\left\{Cos\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
Cost(2,\left\{3 \right\},1)=d[2,3]\, +\, Cost\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
Cost(2,\left\{4 \right\},1)=d[2,4]\, +\, Cost\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
Cost(3,\left\{2 \right\},1)=d[3,2]\, +\, Cost\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
Cost(3,\left\{4 \right\},1)=d[3,4]\, +\, Cost\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
Cost(4,\left\{3 \right\},1)=d[4,3]\, +\, Cost\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
Cost(4,\left\{2 \right\},1)=d[4,2]\, +\, Cost\left ( 2,\Phi ,1 \right )\, =\, 8\, +\, 5\, =\, 13
S = 2
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
Cost(2,\left\{3,4 \right\},1)=min\left\{\begin{matrix} d\left [ 2,3 \right ]\,+ \,Cost\left ( 3,\left\{ 4\right\},1 \right )\, =\, 9\, \, 20\, =\, 29 \\ d\left [ 2,4 \right ]\, \,Cost\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
Cost(3,\left\{2,4 \right\},1)=min\left\{\begin{matrix} d\left [ 3,2 \right ]\,+ \,Cost\left ( 2,\left\{ 4\right\},1 \right )\, =\, 13\, \, 18\, =\, 31 \\ d\left [ 3,4 \right ]\, \,Cost\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
Cost(4,\left\{2,3 \right\},1)=min\left\{\begin{matrix} d\left [ 4,2 \right ]\,+ \,Cost\left ( 2,\left\{ 3\right\},1 \right )\, =\, 8\, \, 15\, =\, 23 \\ d\left [ 4,3 \right ]\, \,Cost\left ( 3,\left\{ 2\right\},1 \right )\, =\, 9\, +\, 18\, =\, 27 \\ \end{matrix}\right.\, =\,23
S = 3
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
Cost(1,\left\{2,3,4 \right\},1)=min\left\{\begin{matrix} d\left [ 1,2 \right ]\,+ \,Cost\left ( 2,\left\{ 3,4\right\},1 \right )\, =\, 10\, \, 25\, =\, 35 \\ d\left [ 1,3 \right ]\, \,Cost\left ( 3,\left\{ 2,4\right\},1 \right )\, =\, 15\, \, 25\, =\, 40 \\ d\left [ 1,4 \right ]\, \,Cost\left ( 4,\left\{ 2,3\right\},1 \right )\, =\, 20\, +\, 23\, =\, 43 \\ \end{matrix}\right.\, =\, 35
最小成本路径为 35。
The minimum cost path is 35.
从成本 {1, {2, 3, 4}, 1} 开始，可得到 d[1, 2] 的最小值。当 s = 3 时，选择从 1 到 2 的路径（成本为 10），然后反向移动。当 s = 2 时，可得到 d[4, 2] 的最小值。选择从 2 到 4 的路径（成本为 10），然后反向移动。
Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards.
当 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）。
When s = 1, we get the minimum value for d [4, 2] but 2 and 4 is already selected. Therefore, we select d [4, 3] (two possible values are 15 for d [2, 3] and d [4, 3], but our last node of the path is 4). Select path 4 to 3 (cost is 9), then go to s = ϕ step. We get the minimum value for d [3, 1] (cost is 6).
