下载文档原格式
算法第二次大作业TSP问题算法分析021251班王昱（02125029）-.问题描述“TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。
TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。
二.算法描述2.1分支界限法2.1.1算法思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
2.1.2算法设计说明设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri 。
在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界［down, up］，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。
对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound(x1) >bound(x1,x2)》bound(x1，…,xn)若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。
再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。
直到一个叶子结点时的可行解X=(x1,…,xn),及目标函数值bound(x1,…,xn)。
2.2 A*算法算法思想对于某一已到达的现行状态，如已到达图中的n节点，它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。
算法综合实验报告学号： 1004111115 姓名：李宏强一、实验内容：分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。
二、程序设计的基本思想、原理和算法描述：（包括程序的数据结构、函数组成、输入/输出设计、符号名说明等）1、动态规划法(1)数据结构：利用二进制来表示集合，则集合S可由一个十进制数x相对应，此x所由一个十进制数x相对应，此x所对应的二进制数为y，如果y的第k位为1，则表示k存在集合S中。
例如：集合S={0，1}（其子集合为{}{0}{1}{01}），我们用二进制数11（所对应十进制数为3）表示S，11中右手边第1个数为1表示0在集合S中，右手边第二个数为1表示1在集合S中，其他位为0表示其它数字不在集合S中；同理,集合S={0,2}（其子集合为{}{0}{2}{02}可用二进制数101（所对应十进制数为5）表示（右手边第1个数为1表示0在集合S中，右手边第二个数为0表示1不在集合S中，右手边第3个数为1表示2在集合S中，则说明0，2在集合中，1不在集合中。
利用邻接矩阵表示任意两点之间的距离例如：mp[i][j]表示点i，j两点之间的距离。
(2)函数组成输入函数in()利用动态规划法算法实现的求解函数solve()主函数main()(3)输入/输出设计本程序可以通过键盘进行输入、屏幕进行输出。
（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）这里采用随机产生输入数据，将数据输出在屏幕上的方式。
(4)符号名说明n 表示顶点个数。
mp[i][j] 表示顶点i和顶点j之间的距离。
dp[i][j] 表示顶点i经过集合S(用二进制表示的数为j)后回到起始点的最短路径和。
(5)算法描述某一个点i不经过任意点回到起始点的最短路径和为mp[i][0](默认初始点为0)dp[i][0] = mp[i][0]; (1<=i<n)点i经过集合S（二进制表示的数为j）的最短路径和为从点i经过集合S中的某一点k后再从该点出发，经过集合S-{k}的最小值。
基于分⽀限界法的旅⾏商问题（TSP）⼀旅⾏推销员问题（英语：Travelling salesman problem, TSP）是这样⼀个问题：给定⼀系列城市和每对城市之间的距离，求解访问每⼀座城市⼀次并回到起始城市的最短回路。
它是组合优化中的⼀个NP困难问题，在运筹学和理论计算机科学中⾮常重要。
分⽀限界法在上⼀篇Blog中我有简单说明，并给出了，这篇⽂章⾥介绍⼀下基于分⽀限界法的TSP算法。
对于TSP，我们需要利⽤上界和下界来对BFS进⾏剪枝，通过不断更新上界和下界，尽可能的排除不符合需求的child，以实现剪枝。
最终，当上限和下限等同时，我们可以获得最优的BFS解，以解决TSP问题。
在第⼀篇中，我们⽤dfs获取上界，⽤每⾏矩阵最⼩值来获取下界。
代码如下，下⾯代码中，我采⽤贪⼼法（使⽤DFS暴⼒搜索到⼀个结果）来获取最初的上界，通过累加每⾏旅⾏商矩阵中的最⼩值来获取⼀个下界。
//分⽀限界法#include<iostream>#include<algorithm>#include<cstdio>#include<queue>const int INF = 100000;const int MAX_N = 22;using namespace std;//n*n的⼀个矩阵int n;int cost[MAX_N][MAX_N];//最少3个点，最多MAX_N个点struct Node{bool visited[MAX_N];//标记哪些点⾛了int s;//第⼀个点int s_p;//第⼀个点的邻接点int e;//最后⼀个点int e_p;//最后⼀个点的邻接点int k;//⾛过的点数int sumv;//经过路径的距离int lb;//⽬标函数的值（⽬标结果）bool operator <(const Node &p)const{return p.lb < lb;//⽬标函数值⼩的先出队列}};priority_queue<Node> pq;//创建⼀个优先队列int low, up;//下界和上界bool dfs_visited[MAX_N];//在dfs过程中搜索过//确定上界,利⽤dfs（属于贪⼼算法），贪⼼法的结果是⼀个⼤于实际值的估测结果int dfs(int u, int k, int l)//当前节点，⽬标节点，已经消耗的路径{if (k == n) return l + cost[u][1];//如果已经检查了n个节点，则直接返回路径消耗+第n个节点回归起点的消耗int minlen = INF, p;for (int i = 1; i <= n; i++){if (!dfs_visited[i] && minlen > cost[u][i])//取与所有点的连边中最⼩的边{minlen = cost[u][i];//找出对于每⼀个节点，其可达节点中最近的节点p = i;}}dfs_visited[p] = true;//以p为下⼀个节点继续搜索return dfs(p, k + 1, l + minlen);}void get_up(){dfs_visited[1] = true;//以第⼀个点作为起点up = dfs(1, 1, 0);}//⽤这种简单粗暴的⽅法获取必定⼩于结果的⼀个值void get_low(){//取每⾏最⼩值之和作为下界low = 0;for (int i = 1; i <= n; i++){//创建⼀个等同于map的临时数组，可⽤memcpyint tmpA[MAX_N];for (int j = 1; j <= n; j++){tmpA[j] = cost[i][j];}sort(tmpA + 1, tmpA + 1 + n);//对临时的数组进⾏排序low += tmpA[1];}}int get_lb(Node p){int ret = p.sumv * 2;//路径上的点的距离的⼆倍int min1 = INF, min2 = INF;//起点和终点连出来的边for (int i = 1; i <= n; i++){//cout << p.visited[i] << endl;if (!p.visited[i] && min1 > cost[i][p.s]){min1 = cost[i][p.s];}//cout << min1 << endl;}ret += min1;for (int i = 1; i <= n; i++){if (!p.visited[i] && min2 > cost[p.e][i]){min2 = cost[p.e][i];}//cout << min2 << endl;}ret += min2;for (int i = 1; i <= n; i++){if (!p.visited[i]){min1 = min2 = INF;for (int j = 1; j <= n; j++){if (min1 > cost[i][j])min1 = cost[i][j];}for (int j = 1; j <= n; j++){if (min2 > cost[j][i])min2 = cost[j][i];}ret += min1 + min2;}}return (ret + 1) / 2;}int solve(){//贪⼼法确定上界get_up();//取每⾏最⼩的边之和作为下界//cout << up << endl;//testget_low();//cout << low << endl;//test//设置初始点,默认从1开始Node star;star.s = 1;//起点为1star.e = 1;//终点为1star.k = 1;//⾛过了1个点for (int i = 1; i <= n; i++){star.visited[i] = false;}star.visited[1] = true;star.sumv = 0;//经过的路径距离初始化star.lb = low;//让⽬标值先等于下界int ret = INF;//ret为问题的解pq.push(star);//将起点加⼊队列while (pq.size()){Node tmp = pq.top();pq.pop();if (tmp.k == n - 1)//如果已经⾛过了n-1个点{//找最后⼀个没有⾛的点int p;for (int i = 1; i <= n; i++){if (!tmp.visited[i]){p = i;//让没有⾛的那个点为最后点能⾛的点break;}}int ans = tmp.sumv + cost[p][tmp.s] + cost[tmp.e][p];//已消耗+回到开始消耗+⾛到P的消耗 //如果当前的路径和⽐所有的⽬标函数值都⼩则跳出if (ans <= tmp.lb){ret = min(ans, ret);break;}//否则继续求其他可能的路径和，并更新上界else{up = min(up, ans);//上界更新为更接近⽬标的ans值ret = min(ret, ans);continue;}}//当前点可以向下扩展的点⼊优先级队列Node next;for (int i = 1; i <= n; i++){if (!tmp.visited[i]){//cout << "test" << endl;next.s = tmp.s;//沿着tmp⾛到next，起点不变next.sumv = tmp.sumv + cost[tmp.e][i];//更新路径和next.e = i;//更新最后⼀个点next.k = tmp.k + 1;//更新⾛过的顶点数for (int j = 1; j <= n; j++) next.visited[j] = tmp.visited[j];//tmp经过的点也是next经过的点 next.visited[i] = true;//⾃然也要更新当前点//cout << next.visited[i] << endl;next.lb = get_lb(next);//求⽬标函数//cout << next.lb << endl;if (next.lb > up) continue;//如果⼤于上界就不加⼊队列pq.push(next);//否则加⼊队列//cout << "test" << endl;}}//cout << pq.size() << endl;BUG:测试为0}return ret;}int main(){cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> cost[i][j];if (i == j){cost[i][j] = INF;}}}cout << solve() << endl;return0;}/*测试5100000 5 61 34 1257 100000 43 20 739 42 100000 8 216 50 42 100000 841 26 10 35 10000036请按任意键继续. . .*/。
旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。
该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。
矚慫润厲钐瘗睞枥庑赖。
关键字：旅行商问题；动态规划法；贪心法；分支限界法1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。
研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。
关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。
归纳起来，目前主要算法可分成传统优化算法和现代优化算法。
在传统优化算法中又可分为：最优解算法和近似方法。
最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。
但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。
聞創沟燴鐺險爱氇谴净。
2正文2.1蛮力法2.1.1蛮力法的设计思想蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。
一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。
在基本的数据结构中，一次处理每个元素的方法是遍历。
残骛楼諍锩瀨濟溆塹籟。
2.1.2算法讨论用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。
如对于图1，我们求解过程如下：酽锕极額閉镇桧猪訣锥。
（1）路径：1->2->3->4->1；路径长度：18；（2）路径：1->2->4->3->1；路径长度：11；（3）路径：1->3->2->4->1；路径长度：23；（4） 路径：1->3->4->2->1；路径长度：11；（5） 路径：1->4->2->3->1；路径长度：18；（6） 路径：1->4->3->2->1；路径长度：18；从中，我们可以知道，路径（2）和（4）路径长度最短。
摘要本文分析比较了tsp问题的动态规划算法，分支界限法，近似等算法。
分析了旅行商问题的时间度特点，针对启发式算法求解旅行商问题中存在的一些问题提出了改进算法。
此算法将群体分为若干小子集，并用启发式交叉算子，以较好利用父代个体的有效信息，达到快速收敛的效果，实验表明此算法能提高寻优速度，解得质量也有所提高。
关键词：旅行商问题TSPAbstractthis paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision.Keywords traveling salesman problem; genetic algorithm; subset; henristic crossover operator目录1、摘要--------------------------------------------------------------12、Abstract---------------------------------------------------------13、Tsp问题的提法------------------------------------------------24、回溯法求Tsp问题--------------------------------------------35、分支限界法求Tsp问题--------------------------------------76、近似算法求解Tsp问题-------------------------------------107、动态规划算法解Tsp问题----------------------------------12引言tsp问题刚提出时，不少人都认为很简单。
TSP问题的解决与实现讲解1. 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并且要求所走的路程最短。
该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
2. 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。
3. 提交报告课程设计报告提交内容包括：(1) 问题描述；(2) 需求分析；(3) 概要设计；(4) 详细设计；(5) 调试分析；(6) 使用说明；(7) 测试结果；(8) 附录（带注释的源程序）。
参见“数据结构课程设计概述.pdf”和“数据结构课程设计示例.pdf”。
指导教师（签字）：系主任（签字）：批准日期：2014年月日1．问题描述（1）题目要求旅行家要旅行n个城市，要求各个城市经历且仅经历一次，最终要回到出发的城市，求出最短路径。
用图论的术语来说，假如有一个图G=(V,E),其中V是顶点集，E是边集，设D=(d)是由ij顶点i和顶点j之间的距离所组成的距离矩阵。
TSP问题就是求出一条通过每个顶点且每个顶点只通过一次的具有最短距离的回路。
（2）基本要求a. 上网查找TSP 问题的应用实例；b. 分析求TSP 问题的全局最优解的时间复杂度；c. 设计一个求近似解的算法；d. 分析算法的时间复杂度。
（3）测试数据5个城市的TSP 问题：注：由于矩阵所表示的是两个城市之间的距离，所以该矩阵为对称矩阵路程矩阵如图所示：最短路径为v 0v 1v 4v 2v 32.需求分析（1）本程序用于求解n 个结点的最短哈密尔顿回路问题。
（2）程序运行后显示提示信息—“Please insert the number of cities:”，例如用户输入5，则表示结点n 的值为5；接下来程序输出提示信息—“Please insert the distance between one city and another:”，例如用户输入测试数据中给出的路程矩阵，表示任意两个城市之间的距离，比如第一个城市到第0个城市之间的距离为25。
TSP问题算法实验报告指导教师：季晓慧姓名：辛瑞乾学号： 1004131114 提交日期： 2015年11月目录总述 (2)动态规划法 (3)算法问题分析 (3)算法设计 (3)实现代码 (3)输入输出截图 (6)OJ提交截图 (6)算法优化分析 (6)回溯法 (6)算法问题分析 (6)算法设计 (7)实现代码 (7)输入输出截图 (9)OJ提交截图 (10)算法优化分析 (10)分支限界法 (10)算法问题分析 (10)算法设计 (10)实现代码 (11)输入输出截图 (15)OJ提交截图 (16)算法优化分析 (16)总结 (16)总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。
动态规划法算法问题分析假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。
首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。
设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。
算法设计输入：图的代价矩阵mp[n][n]输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列（动态规划的边界问题）for(i=1;i<n;i++)dp[i][0]=mp[i][0]2.依次处理每个子集数组x[2^n-1]for(i=1;i<n;i++)if（子集x[j]中不包含i）对x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。
