問題描述：
旅行商問題，即TSP問題（Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。
輸入：
第一行輸入一個整數(shù)n(2<=n<=15)。
輸出：
輸出一行，就是所有路徑之中的最小值。
樣例輸入：
10
42 160 34 136 134 94 78 18 196
42 166 66 106 87 11 122 195 32
160 166 4 98 198 3 154 75 121
34 66 4 187 112 52 94 36 144
136 106 98 187 12 64 45 46 48
134 87 198 112 12 154 109 196 131
94 11 3 52 64 154 11 79 80
78 122 154 94 45 109 11 13 86
18 195 75 36 46 196 79 13 162
196 32 121 144 48 131 80 86 162
樣例輸出：
284
源代碼:
#include <iostream>
#include<stdio.h>
#include<iomanip>
using namespace std;
int main()
{
int n,temp,minDis;
cin>>n;
int dis[n][n]={0}; //dis為距離矩陣
for(int i=0;i<n;i++){ //以下為距離矩陣的初始化
for(int j=0;j<n;j++){
if(j!=i){
cin>>temp;
dis[i][j]=temp;
}
else{
dis[i][j]=1000;
}
}
}
int d[n][1<<(n-1)]; //1<<(n-1)]表示2的n-1次方，d[]為動態(tài)規(guī)劃存儲的城市經(jīng)過矩陣
for(int i=1;i<n;i++){ //將所有城市到第0個城市的路徑初始化為兩市間的距離
d[i][0]=dis[i][0];
}
for(int j=1;j<1<<(n-1);j++){
for(int i=1;i<n;i++){ //j用二進制表示的城市集合
if(((1<<(i-1))&j)==0){ //i不在j表示的城市集合中
minDis=60000;
for(int k=1;k<n;k++){
if(((1<<(k-1))&j)!=0) {//k表示的城市在j表示的城市集合中
temp=dis[i][k]+d[k][j-(1<<(k-1))];
if(temp<minDis){
minDis=temp; //所有k中最小的距離
}
}
}
}
d[i][j]=minDis;
}
}
minDis=60000;
for(int k=1;k<n;k++){
temp=dis[0][k]+d[k][((1<<(n-1))-1)-(1<<(k-1))];
if(minDis>temp){
minDis=temp;
}
}
/* for(int i=0;i<n;i++){ //此部分可以輸出看看形成的d[][]矩陣，便于理解執(zhí)行過程
for(int j=0;j<1<<(n-1);j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
} */
d[0][(1<<(n-1))-1]=minDis;
cout<<d[0][(1<<(n-1))-1];
return 0;
}
關(guān)鍵問題總結(jié)
1.最重要的就是矩陣d[i][j]表示的含義，j是用二進制代碼表示城市是否在集合中，0表示不在，1表示在，這里需要好好看書以及網(wǎng)站博客理解j的含義，前人資料很豐富，就是有些難以理解。
2.子集如何表示？利用二進制位表示
3.移位運算符<<優(yōu)先級很低，一定要加括號
4.循環(huán)的時候要注意先后，j在i的循環(huán)外層，這是由于temp=dis[i][k]+d[k][j-(1<<(k-1))];這句，需要把d[i][j]里j表示的小集合算好了，才能繼續(xù)算j表示的大集合
