TSP问题目录1实验目的 (1)2问题描述与分析 (1)3算法分析 (1)3.1回溯法 (1)3.2 动态规划 (1)3.3 模拟退火算法 (2)4程序设计 (2)4.1回溯法 (2)4.2动态规划算法 (3)4.3模拟退火算法 (4)5实验结果及分析 (5)6实验总结 (6)7源代码 (6)1实验目的1.使用搜索方法进行TSP问题的求解2.了解相关智能算法3.了解NP难问题的求解策略2问题描述与分析某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。

他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。

分析：问题的本质是搜索问题，而且这个问题是NP完全问题，问题的复杂度指数增长，所以普通的搜索无法在有限的时间里完成搜索，尽管有各种优化的算法：启发式算法、深度优先搜索、动态规划、回溯等。

都无法改变复杂度。

实际上大多时候人们并不关心NP完全问题的最优解，只要得出一个近似的解就可以了，因此，人们发明了很多算法，例如粒子群算法、遗传算法、模拟退火算法，这一类算法被称为“智能算法”，但是，他们都无法求出最优解，仅能得到近似解，但这已经足够了。

在本次试验中，一共设计了三个算法：回溯法，动态规划，模拟退火算法。

3算法分析3.1回溯法回溯法采用深度优先方式系统地搜索问题的所有解，基本思路是：确定解空间的组织结构之后，从根结点出发，即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点，这个结点成为新的活结点，并成为当前扩展结点。

如果在当前扩展结点处不能再向纵深方向转移,则当前扩展结点成为死结点。

此时,回溯到最近的活结点处,并使其成为当前扩展结点，回溯到以这种工作方式递归地在解空间中搜索,直到找到所求解空间中已经无活结点为止。

旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……, n的所有排列的递归算法Perm类似，设开始时x=[ 1,2,… n ]，则相应的排列树由x[ 1:n ]的所有排列构成.旅行商问题的回溯算法。

3.2 动态规划设s, s1, s2, …, sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, …, sp, s一定构成一条从s1到s的最短路径，所以TSP问题是构成最优子结构性质的，用动态规划来求解也是合理的。

推导动态规划方程假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

推导：(分情况来讨论)①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的城市3->城市0(0为起点城市)。

此时d(i, V’)=Cis(就是城市i 到城市s 的距离)、②如果V’不为空，那么就是对子问题的最优求解。

你必须在V’这个城市集合中，尝试每一个，并求出最优解。

d(i, V’)=min{Cik +d(k, V’-{k})}注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。

综上所述，TSP问题的动态规划方程就出来了：3.3 模拟退火算法模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

求解TSP的模拟退火算法模型可描述如下:解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为{w1,w2 ,……, wn}，w1, ……, wn是1,2,……,n的一个排列，表明w1城市出发，依次经过w2, ……, wn城市，再返回w1城市。

初始解可选为(1,……, n) ; 目标函数：目标函数为访问所有城市的路径总长度; 我们要求的最优路径为目标函数为最小值时对应的路径。

新路径的产生：随机产生1和n之间的两相异数k和m，不妨假设k<m，则将原(w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn 变为新路径：(w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。

4程序设计4.1回溯法//基本思想：把求解最小值嵌入全排列算法中，对于每一种路径情况，计算其路径长度，然后求出最短路径。

void tsp(int i){int j;//一个全排列完成了if (i == n) {// 位于一个叶子的父节点// 通过增加两条边来完成旅行if (dist[temp_path[n-1]][temp_path[n]]!=0&&dist[temp_path[n]][1]!=0&& (cur_len+dist[temp_path[n-1]][temp_path[n]]+dist[temp_path[n]][1]<min_len||min_len ==0)) {// 找到更优的旅行路径for(j = 1; j <= n; j++)cur_path[j] = temp_path[j];min_len=cur_len+dist[temp_path[n-1]][temp_path[n]] + dist[temp_path[n]][1];} }//构造全排列的过程else {// 尝试子树for (j = i; j <= n; j++)//层中循环+层间递归，整体上是深度优先//能移动到子树x [ j ]吗?if (dist[temp_path[i-1]][temp_path[j]] !=0&&(cur_len+dist[temp_path[i-1]][temp_path[j]]<min_len||min_len == 0)) {//能搜索该子树Swap(&temp_path[i], &temp_path[j]);//第n层的一种情况cur_len += dist[temp_path[i-1]][temp_path[i]];tsp(i+1);//确定一层的某一种情况之后，马上以此情况为基础向下搜索cur_len -= dist[temp_path[i-1]][temp_path[i]];Swap(&temp_path[i], &temp_path[j]);//复原，然后再变成下一种情况}}}4.2动态规划算法基本思想：循环+递归，构造深度优先搜索，然后从后向前每次求解出局部的最短路径，最后合起来就是最短路径。

int SearchMinPath(int n){int CurrentMin = 1000; //int back=index;//int sign=0;if(index==N-1){return dist[n][0];}for(int i=1;i<N;i++){index=back;sign = 0;for(int j=0;j<back;j++){if(i==cur_path[j])sign = 1;}if(sign == 1)continue;cur_path[index++]=i;int temp = dist[n][i] + SearchMinPath(i);if(CurrentMin>temp){CurrentMin = temp;for(int m = 0;m<N-1;m++)exd_path[m]=cur_path[m];}}for(int j=0;j<N-1;j++)cur_path[j]=exd_path[j];return CurrentMin;}4.3模拟退火算法路径变换函数：void reversePath(int *path){int begin,end,len,i;begin = randi(0,n-1);end = randi(0,n-1);if(begin > end) swap(begin,end);len = end - begin + 1;for(i=0;i<len/2;i++)swap(path[begin+i],path[end-i]);}确定是否接受新的解：bool accept(int *curPath,int *exdPath){int curResult = result(curPath);int exdResult = result(exdPath);if(exdResult < curResult)return true;double probability = 0;if(t > 0.000001)probability = exp((curResult - exdResult) / t);if(probability > randf())return true;return false;}褪火过程：while(s!=2){bChange = false;for(i=0;i<L;i++){copyPath(exd_path,cur_path);reversePath(exd_path);if(accept(cur_path,exd_path)){copyPath(cur_path,exd_path);bChange = true;}}t = t * 0.9;if(bChange == false)s++;elses = 0;}5实验结果及分析输入的测试文件：上图是一个10×10的矩阵，代表任意两点之间的距离。

回溯法结果：动态规划运行结果：模拟退火运行结果：分析：以上三种方法，虽然最短长度相同，但路径不同，说明此输入情况有多条最短路径。

6实验总结通过实验基本了解TSP问题基本原理，掌握相关算法的实现！7源代码见随行附件！。