“雞湯惠”幫“鴨湯瑩”看代碼，于是翻出了自己寫的動态規劃法求解TSP問題，于是整理了一下。（算法思想在知識點整理的部分，這裡是具體實作的代碼）
問題描述：
TSP問題是指旅行家要旅行n個城市，要求各個城市經曆且僅經曆一次然後回到出發城市，并要求所走的路程最短。各個城市間的距離可以用代價矩陣來表示。假設從頂點i出發，令d(i, V')表示從頂點i出發經過V'中各個頂點一次且僅一次，最後回到出發點i的最短路徑長度，開始時，V'＝V－{i}，于是，TSP問題的動态規劃函數為：
d(i,V')=min{cik+d(k,V－{k})}(k∈V') （式1）
d(k,{})=cki(k≠i) （式2）
程式清單：
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
#define MAX_IN 10
class 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)
{
cout<<"歡迎來到動态規劃求旅行商問題，請輸入城市個數";
int city_number;
while(cin>>city_number)
{
Tsp tsp(city_number); //初始化城市代價矩陣
tsp.correct(); //糾正使用者輸入的代價矩陣
tsp.printCity(); //列印城市
tsp.getShoretstDistance(); //求出最短路徑
tsp.printProcess(); //列印計算矩陣
cout<<"---------------------------------------"<<endl;
cout<<"歡迎來到動态規劃求旅行商問題，請輸入城市個數";
}
return 0;
}
/*0 3 3 2 6
3 0 7 3 2
3 7 0 2 5
2 3 2 0 3
6 2 5 3 0
*/
/*
0, 10, 20, 30, 40, 50,
12, 0 ,18, 30, 25, 21,
23, 19, 0, 5, 10, 15,
34, 32, 4, 0, 8, 16,
45, 27, 11,10, 0, 18,
56, 22, 16,20, 12, 0，
*/
部分說明：
個人認為動态規劃法求解TSP問題的難點在于（1）求城市（除了起點）之外的其他城市子集；（2）判斷城市是否位于一個子集中。
我遇到的問題是起初認為子集需要按照子集元素的個數從小到大需要排序，在這裡花費了比較多的時間，後來發現其實沒有必要去排序。
（1）關于求子集
例如4個城市{0,1,2,3}，{1,2,3}依次為{}，{1}，{2}，{1,2}，{3}，{1,3}，{2,3}，{1,2,3}，如果用111表示城市321，則上述子集轉換成二進制為0，01，10，001，100,101,110,111，十進制恰好是0,1,2,3,4,5,6,7。雖然子集{1,2}在{3}之前，但周遊子集{1,2}的過程并不會使用過程矩陣中關于3的行列，是以不需要排序。
（2）判斷一個城市是否位于子集中
判斷一個城市是否在子集中，通過位運算(((x>>(i-1))&1)==1來實作，比如集合{1,3,5,6,7}表示成二進制串用1110101，其中集合裡面有的數對應的位數寫成1，沒有的寫成0。要判斷第3位是不是1，就把1110101右移(3-1)位，得到11101，然後結果和00001進行&運算，如果結果是1說明第3位是1，則說明城市在子集中。
（3）填過程矩陣，以process[2][5]為例。
process[2][5] 表示從2出發，通過｛1，3｝，最後回到起點。那麼process[2][5] = min{C21 + process [1][{3}],C23 + process [3][{1}]} = min{C21 + process [1][4],C23 + process [3][1]} ;
從2出發，要去{1,3}。先考慮去1的路，去了1集合{1,3}中隻剩下{3} ,{3}對應二進制100，十進制4,是以要求的process表就是process [1][4],這個4可以通過(101)^(1)得到,(1) = 1<<(1-1);再看去3的路，去了3集合{1,3}中隻剩下{1},{1}對應這1，是以要求的process表就是process [3][1],1通過(101) ^ (100)得到。(100) = 1<<(3-1)。
參考結果：
