旅行商问题（动态规划方法）

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

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

旅行商动态规划算法

让我们考虑一个图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, 令C(S, j)为访问S中每个节点恰好一次、从1开始并在j结束的最短路径的长度。

当|S|> 1时，我们定义C(S,1)= $\propto$，因为路径不能从1开始并在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)

分析

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

示例

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

根据上图，准备下表。

S = $\Phi$

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

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

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

S = 1

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

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

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

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

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

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

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

S = 2

$$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$$

$$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$$

$$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

$$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。

从cost {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]的15和d [4, 3]，但路径的最后一个节点是4）。选择路径4到3（成本为9），然后转到s = ϕ步骤。我们得到d [3, 1]的最小值（成本为6）。

实现

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

#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\n", 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