問題詳情

求解下圖所示的TSP問題，計算出所經過的城市編號以及最短路徑值，城市代價矩陣如圖所示：

求解思路

假設從頂點i出發，令d(i, V’ )表示從頂點i出發經過V’ 中各個頂點一次且僅一次，最后回到出發點（i）的最短路徑長度，開始時， V’ ＝V－{i}，于是，TSP問題的動態規劃函數為：
d(i, V’ )=min{cik+d(k, V’ －{k})} (k∈V’)
d(k,{})=cki (k≠i) (從k出發到達i的距離)

計算過程

從0城市出發經城市1、2、3然后回到0城市的最短路徑長度是：
d(0,{1, 2, 3})=min{c01+d(1, { 2, 3}), c02+d(2, {1, 3}), c03+d(3, {1, 2})}
這是最后一個階段的決策，而：
d(1, {2, 3})=min{c12+d(2, {3}), c13+ d(3, {2})}
d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}
d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}
這一階段的決策又依賴于下面的計算結果：
d(1, {2})= c12+d(2, {}) d(2, {3})=c23+d(3, {})
d(3, {2})= c32+d(2, {}) d(1, {3})= c13+d(3, {})
d(2, {1})=c21+d(1, {}) d(3, {1})=c31+d(1, {})
而下式可以直接獲得（括號中是該決策引起的狀態轉移）：
d(1, {})=c10=5(1→0) d(2, {})=c20=6(2→0) d(3, {})=c30=3(3→0)

再向前倒推，有：
d(1, {2})= c12+d(2, {})=2+6=8(1→2) d(1, {3})= c13+d(3, {})=3+3=6(1→3)
d(2, {3})= c23+d(3, {})=2+3=5(2→3) d(2, {1})= c21+d(1, {})=4+5=9(2→1)
d(3, {1})= c31+d(1, {})=7+5=12(3→1) d(3, {2})= c32+d(2, {})=5+6=11(3→2)
再向前倒退，有：
d(1, {2, 3})= min{c12+d(2, {3}), c13+ d(3, {2})}=min{2+5, 3+11}=7(1→2)
d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}=min{4+6, 2+12}=10(2→1)
d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}=min{7+8, 5+9}=14(3→2)
最后有：
d(0, {1, 2, 3})=min{c01+ d(1, { 2, 3}), c02+ d(2, {1, 3}), c03+ d(3, {1, 2})}
=min{3+7, 6+10, 7+14}=10(0→1)
所以，從頂點0出發的TSP問題的最短路徑長度為10，路徑是0→1→2→3→0。

動態規劃法求解TSP問題的填表過程
假設n個頂點用0～n-1的數字編號，首先生成1～n-1個元素的子集存放在數組V[2n-1]中，設數組d[n][2n-1]存放迭代結果，其中d[i][j]表示從頂點i經過子集V[j]中的頂點一次且僅一次，最后回到出發點0的最短路徑長度。(從頂點0出發)

代碼實現

#include<iostream> #include<iomanip> #include<cmath> using namespace std; #define MAX_IN 10class Tsp { private:int city_number; //城市個數int **distance; //城市距離矩陣int **process; //求最短路徑的過程矩陣 public:Tsp(int city_number); //構造函數void correct(); //矯正輸入的城市代價矩陣void printCity(); //打印城市的距離矩陣void getShoretstDistance(); //動態規劃法求最短路徑void printProcess(); //打印過程矩陣};//構造函數 Tsp::Tsp(int city_num) {int i = 0, j = 0;city_number = city_num;//初始化城市距離矩陣distance = new int*[city_number];cout << "請輸入" << city_number << "個城市之間的距離" << endl;for (i = 0; i<city_number; i++){distance[i] = new int[city_number];for (j = 0; j<city_number; j++)cin >> distance[i][j];}//生成過程矩陣process = new int*[city_number];for (i = 0; i<city_number; i++){process[i] = new int[1 << (city_number - 1)];}}//糾正用戶輸入的城市代價矩陣 void Tsp::correct() {int i;for (i = 0; i<city_number; i++){distance[i][i] = 0;} }//打印城市距離 void Tsp::printCity() {int i, j;//打印代價矩陣cout << "您輸入的城市距離如下" << endl;for (i = 0; i<city_number; i++){for (j = 0; j<city_number; j++)cout << setw(3) << distance[i][j];cout << endl;} }//動態規劃法求最短路徑 void Tsp::getShoretstDistance() {int i, j, k;//初始化第一列for (i = 0; i<city_number; i++){process[i][0] = distance[i][0];}//初始化剩余列for (j = 1; j<(1 << (city_number - 1)); j++){for (i = 0; i<city_number; i++){process[i][j] = 0x7ffff;//設0x7ffff為無窮大//對于數字x，要看它的第i位是不是1，通過判斷布爾表達式 (((x >> (i - 1) ) & 1) == 1的真值來實現if (((j >> (i - 1)) & 1) == 1){continue;}for (k = 1; k<city_number; k++){//不能達到k城市if (((j >> (k - 1)) & 1) == 0){continue;}if (process[i][j]>distance[i][k] + process[k][j ^ (1 << (k - 1))]){process[i][j] = distance[i][k] + process[k][j ^ (1 << (k - 1))];//cout<<i<<"行"<<j<<"列為："<<process[i][j]<<endl;}}}}cout << "最短路徑為" << process[0][(1 << (city_number - 1)) - 1] << endl;}//打印過程矩陣 void Tsp::printProcess() {int i, j;for (j = 0; j<1 << (city_number - 1); j++){cout << setw(3) << j;}cout << endl;for (i = 0; i<city_number; i++){for (j = 0; j<1 << (city_number - 1); j++){if (process[i][j] == 0x7ffff)process[i][j] = -1;cout << setw(3) << process[i][j];}cout << endl;} }//主函數 int main(void) {int city_number;while (cin >> city_number){Tsp tsp(city_number); //初始化城市代價矩陣tsp.correct(); //糾正用戶輸入的代價矩陣tsp.printCity(); //打印城市tsp.getShoretstDistance(); //求出最短路徑tsp.printProcess(); //打印計算矩陣}return 0; }

運行截圖

分析與思考

這個實驗主要借鑒了很多學姐的思想，比如說對某一階段進行判斷，可以采用一維并使用最低為相遇的算法進行判斷，我相信在后面這個地方回流有很多疑問，因為現在天色已經很晚了，這篇博文就直接發了，如果讀者有什么不理解的地方，歡迎進行評論，我們一起針對問題進行交流。

總結

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

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