一、求解TSP问题
1、问题描述

• TSP问题(担货郎问题，旅行商问题)是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短
• 各个城市间的距离可以用代价矩阵来表示。
  
  2、【应用】
  例如：校车怎样以最短的路线行走而接送到所有学生？报纸和牛奶的配送路线怎样最优？循环旅游怎样选取才能实现开支最少？公司视察子公司怎样出差更高效？
  3、【蛮力法求解】
  用蛮力法解决TSP问题，可以找出所有可能的旅行路线，即依次考察图中所有顶点的全排列，从中选取路径长度最短的简单回路。
  
  
  4、证明TSP问题满足最优性原理
  设s,s1,s2, …,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1,s2,…,sp,s一定构成一条从s1到s的最短路径。
  如若不然，设s1,r1,r2,…,rq,s是一条从s1到s的最短路径且经过n-1个不同城市，则s,s1,r1,r2,…,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,…,sp,s要短，从而导致矛盾。所以，TSP问题满足最优性原理。
  5、动态规划法求解过程——示例
  
  6、动态规划求解问题的步骤
  （1）划分子问题—找到“状态”
  
  （2）状态方程
  （3）填表
  
  
  7、算法设计
  （1）【数据结构设计】
  二维数组c[n][n]存放顶点之间的代价，n个顶点用0～n-1的数字编号
  一维数组V[2n-1]存放1～n-1个元素的所有子集
  二维数组dp[n][2n-1]存放递推结果，其中dp[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。
  （2）【动态规划法算法】
  算法——TSP问题
  1．for(i=1; i<n; i++) d[i][0]=c[i][0]; //初始化第0列
  2．for(j=1; j<2n-1-1; j++)
  for(i=1; i<n; i++) //依次进行第i次迭代
  if(子集V[j]中不包含i)
  对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);
  3.对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);
  4．输出最短路径长度d[0][2n-1-1];

8、算法分析

此文章借鉴于博文https://blog.csdn.net/shujian_tianya/article/details/80873892，在此基础上重新进行了分析总结。

一、问题

二、想法

三、讲解

1、怎么求顶点子集，即这些怎么记录？
答：例如4个顶点{0,1,2,3}，{1,2,3}依次为{}，{1}，{2}，{1,2}，{3}，{1,3}，{2,3}，{1,2,3}。十进制数0、1、2、3、4、5、6、7的二进制分别为000、001、010、011、100、101、110、111。上述集合中的元素即为二进制中的位数，例如集合{2,3}，可用二进制110（十进制6）代替，因为二进制110的第一位是0，第二位第三位是1。
整理一下思路——十进制数的二进制表示中，哪位为1则集合中就有哪个数。十进制6的二进制110中，第二三位是1，则6代表集合{2,3}
没有为什么，这是我们定下的一条规则，方便我们解题。
如此，过程矩阵d[i][j]的纵坐标j就多了一个含义。j=0，代表集合{ }；j=1，代表集合{1}……j=5，代表集合{1，3}……以此类推。
大家可能发现一个问题，在4个顶点{0,1,2,3}中，十进制3代表{1,2}，十进制4代表{3}，而我们一般写的集合顺序是{}，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}。集合{3}是第3个，{1,2}是第4个。会发现顺序乱了，这个要说一下，集合之间的排序不影响此题的解答，读者朋友可以将集合以任意顺序写，会发现不影响最终结果的出现。

2、判断一个顶点是否位于子集中
举例解答，如要判断集合j={1,3,5,6,7}是否有顶点3。
集合j={1,3,5,6,7}表示成二进制串为1110101，其中集合里面有的数对应的位数写成1，没有的写成0。要在集合中找顶点3，就是要判断二进制串第3位是不是1，就把1110101右移(3-1)位，得到11101，然后结果和00001进行&运算，如果结果是1说明第3位是1，则说明顶点在子集中。
故判断公式为

(j>>(i-1))&1==1

3、填写过程矩阵过程
arc[i][j]为图的代价矩阵。
d[i][j]为过程矩阵，存放迭代结果。
以d[2][5]为例,d[2][5]=d(2,{1,3})。d[2][5] 表示从2出发，通过｛1，3｝，最后回到起点。那么d[2][5] = min{arc[2][1] + d(1,{3}),arc[2][3] + d(3,{1})} = min{arc[2][1] + d[1][4],arc[2][3] + d[3][1]}。从2出发，要去{1,3}，先考虑去1的路。去了1后集合{1,3}中只剩下{3} ,{3}对应二进制100，十进制4,所以要求的d表就是d[1][4],这个4可以通过(101)^(1)得到,而(1) = 1<<(1-1).其中,二进制101(十进制5)代表集合{1,3};再看去3的路，去了3后集合{1,3}中只剩下{1},{1}对应二进制001，十进制1，所以要求的d表就是d[3][1],1通过(101) ^ (100)得到，而(100) = 1<<(3-1)。故此处又总结出一个公式

d[i][j] = min{arc[i][k] + d[k][j ^ (1 << (k - 1))]}

四、代码

#include<iostream>
#include<iomanip>
using namespace std;
struct rode {
	int x;
	int y;
	int z;
}rode[100][100];//记录过程矩阵中的路线，由点x出发，先经过点k，再经过集合z，过程矩阵j[i][j]中的j就代表集合
int main()
{

	int n, i, j, k, m = 1;
	cout << "顶点个数：";
	cin >> n;
	for (i = 1; i < n; i++)//n个顶点有m个子集，m=2^(n-1)
		m = m * 2;
	//创建动态数组，节省空间
	int **arc = new int*[n];//图的代价矩阵
	for (i = 0; i < n; i++)
		arc[i] = new int[n];
	int **d = new int*[n];//存放迭代结果，即过程矩阵，过程表
	for (i = 0; i < n; i++)
		d[i] = new int[m];
	//输入图的代价矩阵
	cout << "请以矩阵形式输入顶点之间的距离" << endl;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			cin >> arc[i][j];
	//纠正用户输入的数据
	for (i = 0; i < n; i++)
		arc[i][i] = -1;
	cout << "您输入的顶点之间的距离如下" << endl;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			cout << setw(3) << arc[i][j];
		cout << endl;
	}
	//初始化第0列
	for (i = 0; i < n; i++)
		d[i][0] = arc[i][0];
	//填过程矩阵，第一行，因为第一行代表从顶点0开始经过一些顶点再回到0，但是我们只需要d[0][m-1]这一个值，所以第一行先不计算，等最后再只计算d[0][m-1]，节省时间。
	for (j = 1; j < m; j++)//j就代表m个子集，如j=5(二进制为101)代表{1,3}，j=3(二进制为011)代表{1,2}。二进制1011就代表集合{1,2,4}。这是设定的一种规则。
	{
		for (i = 1; i < n; i++)
		{
			d[i][j] = 0x7ffff;//设0x7ffff为无穷大
			if (((j >> (i - 1)) & 1) == 1)	//对于数字x，要看它的第i位是不是1，通过判断布尔表达式 (((x >> (i - 1) ) & 1) == 1的真值来实现
				continue;					//若第i位是1，就说明子集j里包含i这个元素，d[i][j]这个空就无需计算
			for (k = 1; k < n; k++)
			{
				/*找出集合j中有哪些元素，比如，(6>>(2-1))&1==1,说明集合{2.3}中有元素2。之所以这么做，
				是因为我们人知道j=6（二进制110）代表集合{2.3}，但是计算机不知道，所以要有找元素这一步*/
				if (((j >> (k - 1)) & 1) == 0)	//集合中没有此元素就跳过
					continue;
				/*以d[2][5]为例,d[2][5]=d(2,{1,3})。d[2][5] 表示从2出发，通过｛1，3｝，最后回到起点。
				那么d[2][5] = min{arc[2][1] + d(1,{3}),arc[2][3] + d(3,{1})} = min{arc[2][1]  + d[1][4],arc[2][3] + d[3][1]}。
				从2出发，要去{1,3}，先考虑去1的路。去了1后集合{1,3}中只剩下{3} ,{3}对应二进制100，十进制4,所以要求的d表就是d[1][4],这个4可以通过(101)^(1)得到,而(1) = 1<<(1-1).其中,二进制101(十进制5)代表集合{1,3};
				再看去3的路，去了3后集合{1,3}中只剩下{1},{1}对应二进制001，十进制1，所以要求的d表就是d[3][1],1通过(101) ^ (100)得到，而(100) = 1<<(3-1)。*/
				if (d[i][j] > arc[i][k] + d[k][j ^ (1 << (k - 1))])
				{
					d[i][j] = arc[i][k] + d[k][j ^ (1 << (k - 1))];
					rode[i][j].x = i;
					rode[i][j].y = k;
					rode[i][j].z = j ^ (1 << (k - 1));//由x出发，先经过k，再经过集合z
				}
			}
		}
	}
	//计算d[0][m-1]，d(0,{1,2,3})=min{arc[0][1]+d(1,{2,3}),arc[0][2]+d(2,{1,3}),arc[2][3]+d(3,{1,2})}
	for (j = 0; j < m - 1; j++)
		d[0][j] = -1;
	d[0][m - 1] = 0x7ffff;
	for (k = 1; k < n; k++)
	{
		
		if ((( m-1 >> (k - 1)) & 1 ) == 0)	
			continue;
		if (d[0][m - 1] > arc[0][k] + d[k][(m - 1) ^ (1 << (k - 1))])
		{
			d[0][m - 1] = arc[0][k] + d[k][(m - 1) ^ (1 << (k - 1))];
			rode[0][m - 1].x = 0;
			rode[0][m - 1].y = k;
			rode[0][m - 1].z = (m - 1) ^ (1 << (k - 1));
		}
	}
	cout << "最短路径为：" << d[0][m-1] << endl;
	//输出路线
	j = m - 1;
	cout << "0→";
	for (i=0;i<n-1;i++)
	{
		cout << rode[i][j].y << "→";
		j = rode[i][j].z;
	}
	cout<< rode[i][j].y << endl;
	//输出过程矩阵
	cout << "过程矩阵为：" << endl;
	cout << '\t';
	for (j = 0; j < m; j++)
		cout << j << '\t';
	cout << endl;
	for (i = 0; i < n; i++)
	{
		cout << i << '\t';
		for (j = 0; j < m; j++)
		{
			if (d[i][j] == 0x7ffff)
				d[i][j] = -1;
			cout << d[i][j] << '\t';
		}
		cout << endl;
	}
	return 0;
}

五、结果截图

问题详情

求解下图所示的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 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)
{
	int city_number;
	while (cin >> city_number)
	{
		Tsp tsp(city_number);		//初始化城市代价矩阵
		tsp.correct();					//纠正用户输入的代价矩阵
		tsp.printCity();				//打印城市
		tsp.getShoretstDistance();		//求出最短路径
		tsp.printProcess();			//打印计算矩阵
	}
	return 0;
}

运行截图

分析与思考

这个实验主要借鉴了很多学姐的思想，比如说对某一阶段进行判断，可以采用一维并使用最低为相遇的算法进行判断，我相信在后面这个地方回流有很多疑问，因为现在天色已经很晚了，这篇博文就直接发了，如果读者有什么不理解的地方，欢迎进行评论，我们一起针对问题进行交流。