旅行商問題（動態規劃方法）

旅行商問題是最臭名昭著的計算問題。我們可以使用蠻力法來評估所有可能的路線並選擇最佳路線。對於圖中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