动态规划法求解TSP问题 C++

本文主要是介绍动态规划法求解TSP问题 C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

“鸡汤惠”帮“鸭汤莹”看代码，于是翻出了自己写的动态规划法求解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 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)
{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)。

参考结果：