旅行商问题（动态方法）

更新于 2025/10/16 16:21:06

旅行商动态规划算法
实现

旅行商问题是最著名的计算问题。我们可以用蛮力法评估每条可能的路径，并选择最佳路径。对于图中的 n 个顶点，有 (n−1)! 种可能性。因此，保持了更高的复杂度。

然而，与使用蛮力法相比，使用动态规划方法可以在更短的时间内获得解决方案，尽管没有多项式时间算法。

旅行商动态规划算法

考虑一个图G = (V,E)，其中V是一组城市，E是一组带权边。边e(u, v)表示顶点u和v相连。顶点u和v之间的距离为d(u, v)，它应该是非负的。

假设我们从城市1出发，在访问了一些城市之后，现在到达了城市j。因此，这是一次部分游览。我们当然需要知道 j，因为这将决定接下来哪些城市最方便游览。我们还需要知道迄今为止访问过的所有城市，这样我们就不会重复游览任何一个城市。因此，这是一个合适的子问题。

对于包含 1 和 j 的城市子集 S $\epsilon$ {1,2,3,...,n}，其中 $\epsilon$ S，设 C(S, j) 为最短路径的长度，该路径访问 S 中每个节点一次，起始于 1，终止于 j。

当 |S|> 1 时，我们定义 𝑪C(S,1)= $\propto$，因为路径不能以 1 为起点和终点。

现在，让我们用更小的子问题来表示 C(S, j)。我们需要从 1 开始，终止于 j。我们应该这样选择下一个城市：

$$C\left ( S,j ight )\, =\, min\, C\left ( S\, -\, \left\{j ight\},i ight )\, +\, d\left ( i,j ight )\: where\: i\: \epsilon \: S\: and\: i eq 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)

分析

最多有 2ⁿ.n 个子问题，每个子问题的求解时间为线性时间。因此，总运行时间为 O(2ⁿ.n²)。

示例

在以下示例中，我们将说明解决旅行商问题的步骤。

根据上图，可以得出下表。

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = $\Phi$

$$Cost\left ( 2,\Phi ,1 ight )\, =\, d\left ( 2,1 ight )\,=\,5$$

$$Cost\left ( 3,\Phi ,1 ight )\, =\, d\left ( 3,1 ight )\, =\, 6$$

$$Cost\left ( 4,\Phi ,1 ight )\, =\, d\left ( 4,1 ight )\, =\, 8$$

S = 1

$$Cost(i,s)=min\left\{Cos\left ( j,s-(j) ight )\, +\,d\left [ i,j ight ] ight\}$$

$$Cost(2,\left\{3 ight\},1)=d[2,3]\, +\, Cost\left ( 3,\Phi ,1 ight )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(2,\left\{4 ight\},1)=d[2,4]\, +\, Cost\left ( 4,\Phi ,1 ight )\, =\, 10\, +\, 8\, =\, 18$$

$$Cost(3,\left\{2 ight\},1)=d[3,2]\, +\, Cost\left ( 2,\Phi ,1 ight )\, =\, 13\, +\, 5\, =\, 18$$

$$Cost(3,\left\{4 ight\},1)=d[3,4]\, +\, Cost\left ( 4,\Phi ,1 ight )\, =\, 12\, +\, 8\, =\, 20$$

$$Cost(4,\left\{3 ight\},1)=d[4,3]\, +\, Cost\left ( 3,\Phi ,1 ight )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(4,\left\{2 ight\},1)=d[4,2]\, +\, Cost\left ( 2,\Phi ,1 ight )\, =\, 8\, +\, 5\, =\, 13$$

S = 2

$$Cost(2,\left\{3,4 ight\},1)=min\left\{\begin{matrix} d\left [ 2,3 ight ]\,+ \,Cost\left ( 3,\left\{ 4 ight\},1 ight )\, =\, 9\, +\, 20\, =\, 29 \ d\left [ 2,4 ight ]\,+ \,Cost\left ( 4,\left\{ 3 ight\},1 ight )\, =\, 10\, +\, 15\, =\, 25 \ \end{matrix} ight.\, =\,25$$

$$Cost(3,\left\{2,4 ight\},1)=min\left\{\begin{matrix} d\left [ 3,2 ight ]\,+ \,Cost\left ( 2,\left\{ 4 ight\},1 ight )\, =\, 13\, +\, 18\, =\, 31 \ d\left [ 3,4 ight ]\,+ \,Cost\left ( 4,\left\{ 2 ight\},1 ight )\, =\, 12\, +\, 13\, =\, 25 \ \end{matrix} ight.\, =\,25$$

$$Cost(4,\left\{2,3 ight\},1)=min\left\{\begin{matrix} d\left [ 4,2 ight ]\,+ \,Cost\left ( 2,\left\{ 3 ight\},1 ight )\, =\, 8\, +\, 15\, =\, 23 \ d\left [ 4,3 ight ]\,+ \,Cost\left ( 3,\left\{ 2 ight\},1 ight )\, =\, 9\, +\, 18\, =\, 27 \ \end{matrix} ight.\, =\,23$$

S = 3

$$Cost(1,\left\{2,3,4 ight\},1)=min\left\{\begin{matrix} d\left [ 1,2 ight ]\,+ \,Cost\left ( 2,\left\{ 3,4 ight\},1 ight )\, =\, 10\, +\, 25\, =\, 35 \ d\left [ 1,3 ight ]\,+ \,Cost\left ( 3,\left\{ 2,4 ight\},1 ight )\, =\, 15\, +\, 25\, =\, 40 \ d\left [ 1,4 ight ]\,+ \,Cost\left ( 4,\left\{ 2,3 ight\},1 ight )\, =\, 20\, +\, 23\, =\, 43 \ \end{matrix} ight.\, =\, 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）。

实现

以下是上述方法在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <limits.h>
#define MAX 9999
int n = 4;
int distan[20][20] = {
   {0, 22, 26, 30},
   {30, 0, 45, 35},
   {25, 45, 0, 60},
   {30, 35, 40, 0}};
int DP[32][8];
int TSP(int mark, int position) {
   int completed_visit = (1 << n) - 1;
   if (mark == completed_visit) {
       return distan[position][0];
   }
   if (DP[mark][position] != -1) {
       return DP[mark][position];
   }
   int answer = MAX;
   for (int city = 0; city < n; city++) {
      if ((mark & (1 << city)) == 0) {
         int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);
         answer = (answer < newAnswer) ? answer : newAnswer;
      }
   }
   return DP[mark][position] = answer;
}
int main() {
   for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < n; j++) {
         DP[i][j] = -1;
      }
   }
   printf("Minimum Distance Travelled -> %d
", TSP(1, 0));
   return 0;
}

输出

Minimum Distance Travelled -> 122

#include<iostream>
using namespace std;
#define MAX 9999
int n=4;
int distan[20][20] = {{0, 22, 26, 30},
   {30, 0, 45, 35},
   {25, 45, 0, 60},
   {30, 35, 40, 0}
};
int completed_visit = (1<<n) -1;
int DP[32][8];
int TSP(int mark, int position){
   if(mark==completed_visit) {
      return distan[position][0];
   }
   if(DP[mark][position]!=-1) {
      return DP[mark][position];
   }
   int answer = MAX;
   for(int city=0; city<n; city++) {
      if((mark&(1<<city))==0) {
         int newAnswer = distan[position][city] + TSP( mark|(1<<city),city);
         answer = min(answer, newAnswer);
      }
   }
   return DP[mark][position] = answer;
}
int main(){
   for(int i=0; i<(1<<n); i++) {
      for(int j=0; j<n; j++) {
         DP[i][j] = -1;
      }
   }
   cout << "Minimum Distance Travelled -> " << TSP(1,0);
   return 0;
}

输出

Minimum Distance Travelled -> 122

public class Main {
   static int n = 4;
   static int[][] distan = {
      {0, 22, 26, 30},
      {30, 0, 45, 35},
      {25, 45, 0, 60},
      {30, 35, 40, 0}
   };
   static int completed_visit = (1 << n) - 1;
   static int[][] DP = new int[32][8];
   static int TSP(int mark, int position) {
      if (mark == completed_visit) {
         return distan[position][0];
      }
      if (DP[mark][position] != -1) {
         return DP[mark][position];
      }
      int answer = Integer.MAX_VALUE;
      for (int city = 0; city < n; city++) {
         if ((mark & (1 << city)) == 0) {
            int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);
            answer = Math.min(answer, newAnswer);
         }
      }
      DP[mark][position] = answer;
      return answer;
   }
   public static void main(String[] args) {
      for (int i = 0; i < (1 << n); i++) {
         for (int j = 0; j < n; j++) {
             DP[i][j] = -1;
         }
      }
      System.out.println("Minimum Distance Travelled -> " + TSP(1, 0));
   }
}

输出

Minimum Distance Travelled -> 122

import sys
n = 4
distan = [[0, 22, 26, 30],
          [30, 0, 45, 35],
          [25, 45, 0, 60],
          [30, 35, 40, 0]]
completed_visit = (1 << n) - 1
DP = [[-1 for _ in range(n)] for _ in range(2 ** n)]
def TSP(mark, position):
    if mark == completed_visit:
        return distan[position][0]
    if DP[mark][position] != -1:
        return DP[mark][position]
    answer = sys.maxsize
    for city in range(n):
        if (mark & (1 << city)) == 0:
            new_answer = distan[position][city] + TSP(mark | (1 << city), city)
            answer = min(answer, new_answer)
    DP[mark][position] = answer
    return answer
for i in range(1 << n):
    for j in range(n):
        DP[i][j] = -1
print("Minimum Distance Travelled ->", TSP(1, 0))

输出

Minimum Distance Travelled -> 122

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

旅行商问题（动态方法）

旅行商动态规划算法

分析

示例

实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！