#include <iostream> #include <cmath> using namespace std; //集合虛擬化用000 、001 、010 、011 、100 、101 、110 、111分別表示{} 、{1}（V[2^(1-1)]） 、{2}（V[2^(2-1)]） 、{1,2}（V[2^(1-1)+2^(2-1)]） 、{3}（V[2^(3-1)]） 、{1,3}（V[2^(1-1)+2^(3-1)]） 、{2,3}（V[2^(2-1)+2^(3-1)]） 、{1,2,3}（V[2^(1-1)+2^(2-1)+2^(3-1)]）注意{1,2} 、{3}順序 //這是本題的難點，將十進制數轉化為二進制 //①直觀的看出來包含的元素②可以直接用編碼表示這個集合 int distanceTable[100][100];//需要填的表格 int distanceMatrix[10][10];//城市距離的代價矩陣 int N;//城市數量 int path[100][100];//若path[i][j] = k,則說明從i到集合V[j]的最短距離是從i到集合V[j]中的k int cinDistance(){//輸入代價矩陣cout<<"請輸入城市個數"<<endl;cin>>N;cout<<"請輸入城市距離的代價矩陣"<<endl;for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {cin>>distanceMatrix[i][j];}}for (int k = 0; k < N; ++k) {//規范distanceMatrix[k][k] = 0;}cout<<"您的代價矩陣已被規范化"<<endl;for (int i = 0; i < N; ++i) {for (int j = 0; j < (int)pow(2,N); ++j) {distanceTable[i][j] = -1;}}return 0; }int exist(int i,int j){//判斷集合V[j]中是否有元素i,有則返回1if((int)pow(2,i - 1)&j)return 1;else return 0; }int TSP(){for (int i = 1; i < N; ++i) {//初始化第0列,i為行數distanceTable[i][0] = distanceMatrix[i][0];} //第一步，先不填最后一個空，先填前面的for (int j = 1; j < (int)pow(2,N - 1); ++j) {//從第一列開始填表,j為列數for (int i = 1; i < N; ++i) {//從第一行開始int min = 10000;if(!exist(i,j)){//如果集合V[j]中沒有元素i，則求i到V[j]再到0的最短路徑for (int k = 1; k < N; ++k) {if(exist(k,j)){//如果k存在集合V[j]中，則求i到k + (k再到0的最短距離)//int d = distanceMatrix[i][k] + distanceTable[k][j - (int)pow(2,k - 1)];//這一行很難理解，為什么V[j]中除掉看，就是//集合V[j - (int)pow(2,k - 1)]呢，因為 例如V[5]={1,3}他的編碼是101，如果去掉3，即是101 - 2的3次方 = 101 - 100 = 001，可知集合只剩下1了,所以就是集合001了V[1]/if(d < min){path[i][j] = k;//即從i到V[j]再到0的最短距離是先從i到kmin = d;}}}distanceTable[i][j] = min;}}} //填最后一個空也就是求最短路徑長度，并求最短路徑int min = 1000;for (int k = 1; k < N; ++k) {int d = distanceMatrix[0][k] + distanceTable[k][((int)pow(2,N - 1) - 1) - (int)pow(2,k - 1)];if(d < min){min = d;path[0][(int)pow(2,N - 1) - 1] = k;}}distanceTable[0][((int)pow(2,N - 1) - 1)] = min;return 0; }int coutResult(){for (int i = 0; i < N; ++i) {//輸出表格for (int j = 0; j < (int)pow(2,N - 1); ++j) {cout<<distanceTable[i][j]<<'\t';}cout<<endl;}//輸出路徑cout<<"0->";int i = 0;for (int j = (int)pow(2,N - 1) - 1; j > 0;) {i = path[i][j];cout<<i<<"->";j = j - (int)pow(2,i - 1);}cout<<"0"<<endl;return 0; }int main() {cinDistance();TSP();coutResult();return 0; }

總結

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

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