C++ 動態規劃求解TSP（旅行商問題）

• 動態規劃“四部曲”
• TSP問題介紹
• 使用動態規劃分析TSP
• • 問題結構分析
  • • • • ==給出問題表示==
        • ==明確原始問題==
  • 遞推關系建立
  • • • • ==分析最優（子）結構==
        • ==構造遞推公式==
  • 確定計算順序
  • 最優方案追蹤
  • C++代碼
  • 時間復雜度分析

動態規劃“四部曲”

問題結構分析： 給出問題表示，明確原始問題。

遞推關系建立： 分析最優（子）結構，構造遞推公式。

確定計算順序： 確定計算順序，依次求解問題。

最優方案追蹤： 記錄決策過程，輸出最優方案。

TSP問題介紹

旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個人要拜訪n個城市，從當前所在城市出發，經過且僅經過一次所有城市，回到出發的城市。選擇一條路徑使得其路程為所有路徑中的最小值。

使用動態規劃分析TSP

問題結構分析

給出問題表示

D[location , V]：從當前所在城市location經過V‘集合（剩余未訪問城市的集合）的最短路徑。

明確原始問題

D[i , V]：從當前所在城市location經過V‘集合（剩余未訪問城市的集合）的最短路徑。

遞推關系建立

分析最優（子）結構

D[i , V] = C_ik + D[k , V - {k} ]

構造遞推公式

當V‘為空集時，此時所有頂點均被訪問過，直接回到起始頂點即可。（a代表起始點）

$$\{\begin{array}{c}Cia,V=\{\}且i=a\\ min\{Cik+D[k,V?k]\}，V=\{\}\end{array}$$

確定計算順序

?：可以直接求得。
?：不存在該路徑。
D[2,{1,3}] = min{ C₂₁+D[1,{}] , C₂₃ + D[3,{}] }

{}{1}{2}{1,2}{3}{1,3}{2,3}{1,2,3}

i=1	?	?		?		?		?
i=2	?		?	?		D[2,{1,3}]	?	?
i=3	?				?	?	?	?

由表格發現，D[2,{1,3}]依賴其左邊部分的子問題，確定計算順序由左到右。從不同頂點出發的最優解在表中的位置不同。

最優方案追蹤

創建一個Rec數組用于存放決策，記錄前驅節點。

{}{1}{2}{1,2}{3}{1,3}{2,3}{1,2,3}

i=1		?		?		?		?
i=2			?	?			?	?
i=3					?	?	?	?

C++代碼

創建二維數組求解、追蹤最優解，對于n頂點的圖，需要創建一個n*2ⁿ的二維數組，對于前一部分中列的排序為什么是{}、{1}、{2}、{1,2}、{3}、{1,3}、{2,3}、{1,2,3}，大家可能存在疑問，實際上這是為了方便編寫代碼，使用數字的二進制表示集合中存在的元素，例如000（第0列）表示空集，111（第7列）表示{1,2,3}。

#include<iostream> #include<cmath> using namespace std; #define N 9999 //TSP問題求解函數 void TSP(int n,int** graph,int location){//構建二維數組[i,2^n]，j模擬集合個數int **D = new int*[n+1]; //建行0～n，為方便理解和表示，第0行未使用int **Rec = new int*[n+1]; //建立Recfor(int i=1;i<=n;i++){//建列表示集合D[i] = new int [(int)pow(2,n)]; Rec[i] = new int [(int)pow(2,n)];}//初始化D、Recfor(int i=1;i<=n;i++){D[i][0]=graph[i][location]; //D[i,{}]Rec[i][0]= -1;for(int j=1;j<=(int)pow(2,n)-1;j++){D[i][j]=N;Rec[i][j] = -1;}}//動態規劃for(int j=1;j<=(int)pow(2,n)-1;j++){ //對每一列求解for(int i=1;i<=n;i++){ //每一行找最短路徑int min = N;if(((int)pow(2,i-1) & j) == 0){ //頂點集不能包含iint length = N;for(int k=1;k<=n;k++){if((int)pow(2,k-1) & j ){ //若頂點在集合中length = graph[i][k] + D[k][j-(int)pow(2,k-1)];if(length < min){min = length;D[i][j] = min;Rec[i][j] = k;//局部最優決策}}}}}}cout<<"最短長度："<<D[location][(int)pow(2,n)-1-(int)pow(2,location-1)]<<endl;//最短路徑長度cout<<"最短路徑為："<<location;int row = location;int column = (int)pow(2,n)-1-(int)pow(2,row-1);while(column > 0){cout<< "->"<<Rec[row][column];row = Rec[row][column];column -= (int)pow(2,row-1);}cout<<"->"<<location<<endl; }int main(){cout<<"旅行家需要游歷多少個城市？："<<endl;int n;cin>>n;//建立二維數組模擬鄰接矩陣int **graph=new int* [n+1];for(int i=1;i<=n;i++)graph[i] = new int[n+1];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<"輸入鄰接矩陣graph["<<i<<"]["<<j<<"]的權："<<endl;cin>>graph[i][j];}}cout<<"旅行家現在在第幾個城市？"<<endl;int location;cin>>location;TSP(n,graph,location); //TSP求解return 0; }

時間復雜度分析

如代碼所示，求解TSP問題時間花費最主要在n*2ⁿ的二維數組的操作上，故時間復雜度為O(n*2ⁿ),時間復雜度隨n的增大呈指數爆炸增長。

總結

以上是生活随笔為你收集整理的C++ 动态规划求解TSP（旅行商问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。