分支限界法——TSP问题讲诉

算法第二次大作业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.输出最短路径长度。

标题：算法分支限界法在货郎担问题中的应用摘要：分支限界法是一种高效的解决组合优化问题的算法，本文将详细介绍分支限界法在货郎担问题中的应用，包括问题的描述、算法原理、实现步骤以及案例分析等内容。

一、问题描述货郎担问题，又称为旅行商问题（TSP），是一个经典的组合优化问题。

问题的描述为：有n个城市，货郎担需要从一个城市出发，经过所有的城市且只经过一次，最后回到出发的城市，要求找到一条最短的路径。

这是一个NP-hard问题，传统的穷举法在城市数量较大时难以找到最优解。

二、算法原理分支限界法是一种以深度优先搜索为基础的优化算法。

其核心思想是根据当前问题状态的下界（或上界）对搜索空间进行剪枝，从而减少搜索空间，提高搜索效率。

在货郎担问题中，分支限界法通过动态规划的方式记录已经访问过的城市，从而避免重复计算，同时利用启发式信息（如最近邻居、最小生成树等）进行路径选择，不断更新路径的下界，直至找到最优解或者搜索空间被完全剪枝。

三、实现步骤1. 初始化：设置初始的城市路径、已访问城市集合、路径长度、下界等参数。

2. 搜索：利用深度优先搜索，根据当前路径确定下一个访问的城市，并更新路径长度和下界。

3. 剪枝：根据当前路径长度与下界的关系，对搜索空间进行剪枝。

4. 回溯：如果搜索路径无法继续扩展，进行回溯，更新路径状态。

5. 结束条件：当所有城市都被访问过一次后，得到一条完整的路径，更新最优解。

四、案例分析假设有5个城市，它们的坐标为：A(0, 0)、B(1, 2)、C(3, 1)、D(5, 3)、E(4, 0)利用分支限界法求解货郎担问题，我们按照以下步骤进行计算：（1）初始化：选择一个城市作为出发点，并初始化已访问城市集合、路径长度和下界。

（2）搜索：根据当前路径选择下一个访问的城市，并更新路径长度和下界。

（3）剪枝：根据当前路径长度与下界的关系，进行搜索空间的剪枝。

（4）回溯：如果搜索路径无法继续扩展，进行回溯，更新路径状态。

摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(Nondeterministic Polynomial)难题.关键词:旅行商问题求解算法比较一.引言旅行商问题(Travelling Salesman Problem),是计算机算法中的一个经典的难解问题,已归为NP一完备问题类.围绕着这个问题有各种不同的求解方法,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,甚至是较好的解释.所以我认为很多问题有快速的算法(多项式算法),但是,也有很多问题是无法用算法解决的.事实上,已经证明很多问题不可能在多项式时间内解决出来.但是,有很多很重要的问题他们的解虽然很难求解出来,但是他们的值却是很容易求可以算出来的.这种事实导致了NP完全问题.NP表示非确定的多项式,意思是这个问题的解可以用非确定性的算法"猜"出来.如果我们有一个可以猜想的机器,我们就可以在合理的时间内找到一个比较好的解.NP-完全问题学习的简单与否,取决于问题的难易程度.因为有很多问题,它们的输出极其复杂,比如说人们早就提出的一类被称作NP-难题的问题.这类问题不像NP-完全问题那样时间有限的.因为NP-问题由上述那些特征,所以很容易想到一些简单的算法――把全部的可行解算一遍.但是这种算法太慢了(通常时间复杂度为O(2^n))在很多情况下是不可行的.现在,没有知道有没有那种精确的算法存在.证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了,或许你就是成功者.本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发,不重复地走完其余N—1个城市,并回到原出发点,在所有可能的路径中求出路径长度最短的一条,比较是否是最优化,哪种结果好.二.求解策略及优化算法动态规划法解TSP问题我们将具有明显的阶段划分和状态转移方程的规划称为动态规划,这种动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析.在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦.一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决.所以动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的,相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略.旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话,它只取其中的一个.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算.关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k 个城市的可能集合,动态规划的递推关系为:gk(i,S)=min[gk-1(j,S\{j})+dji] j属于S,dji表示j-i的距离.或者我们可以用:f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路径.f(S,v)=min { f(S-{u},u)+dist(v,u) }u in Sf(V,1)即为所求2.分支限界法解TSP问题旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜索类似,使用一个优先队列,队列中的每个元素中都包含到达根的路径.假设我们要寻找的是最小耗费的旅行路径,那可以使用最小耗费分枝定界法.在实现过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为M i n H e ap N o d e.每个节点包括如下区域: x(从1到n的整数排列,其中x [ 0 ] = 1 ),s(一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [ s + 1 : n - 1 ]),c c(旅行路径前缀,即解空间树中从根节点到当前节点的耗费),l c o s t(该节点子树中任意叶节点中的最小耗费), rc o s t(从顶点x [ s : n - 1 ]出发的所有边的最小耗费之和).当类型为M i n He a p N o d e ( T )的数据被转换成为类型T时,其结果即为l c o s t的值.分枝定界算法的代码见程序.程序首先生成一个容量为1 0 0 0的最小堆,用来表示活节点的最小优先队列.活节点按其l c o s t 值从最小堆中取出.接下来,计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费M i n O u t.如果某些顶点没有出边,则有向图中没有旅行路径,搜索终止.如果所有的顶点都有出边,则可以启动最小耗费分枝定界搜索.根的孩子(图1 6 - 5的节点B)作为第一个E-节点,在此节点上,所生成的旅行路径前缀只有一个顶点1,因此s=0, x[0]=1, x[1:n-1]是剩余的顶点(即顶点2 , 3 ,., n ).旅行路径前缀1 的开销为0 ,即c c = 0 ,并且,r c o st=n i=1M i n O u t .在程序中,bestc 给出了当前能找到的最少的耗费值.初始时,由于没有找到任何旅行路径,因此b e s t c的值被设为N o E d g e. 程序旅行商问题的最小耗费分枝定界算法templateT AdjacencyWDigraph::BBTSP(int v[]){// 旅行商问题的最小耗费分枝定界算法// 定义一个最多可容纳1 0 0 0个活节点的最小堆MinHeap > H(1000);T *MinOut = new T [n+1];// 计算MinOut = 离开顶点i的最小耗费边的耗费T MinSum = 0; // 离开顶点i的最小耗费边的数目for (int i = 1; i <= n; i++) {T Min = NoEdge;for (int j = 1; j <= n; j++)if (a[j] != NoEdge &&(a[j] < Min || Min == NoEdge))Min = a[j];if (Min == NoEdge) return NoEdge; // 此路不通MinOut = Min;MinSum += Min;}// 把E-节点初始化为树根MinHeapNode E;E.x = new int [n];for (i = 0; i < n; i++)E.x = i + 1;E.s = 0; // 局部旅行路径为x [ 1 : 0 ] = 0; // 其耗费为0E.rcost = MinSum;T bestc = NoEdge; // 目前没有找到旅行路径// 搜索排列树while (E.s < n - 1) {// 不是叶子if (E.s == n - 2) {// 叶子的父节点// 通过添加两条边来完成旅行// 检查新的旅行路径是不是更好if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && ( + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge)) {// 找到更优的旅行路径bestc = + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]; = bestc;E.lcost = bestc;E . s + + ;H . I n s e r t ( E ) ; }else delete [] E.x;}else {// 产生孩子for (int i = E.s + 1; i < n; i++)if (a[E.x[E.s]][E.x] != NoEdge) {// 可行的孩子, 限定了路径的耗费T cc = + a[E.x[E.s]][E.x];T rcost = E.rcost - MinOut[E.x[E.s]];T b = cc + rcost; //下限if (b < bestc || bestc == NoEdge) {// 子树可能有更好的叶子// 把根保存到最大堆中MinHeapNode N;N.x = new int [n];for (int j = 0; j < n; j++)N.x[j] = E.x[j];N.x[E.s+1] = E.x;N.x = E.x[E.s+1]; = cc;N.s = E.s + 1;N.lcost = b;N.rcost = rcost;H . I n s e r t ( N ) ; }} // 结束可行的孩子delete [] E.x;} // 对本节点的处理结束try {H.DeleteMin(E);} // 取下一个E-节点catch (OutOfBounds) {break;} // 没有未处理的节点}if (bestc == NoEdge) return NoEdge; // 没有旅行路径// 将最优路径复制到v[1:n] 中for (i = 0; i < n; i++)v[i+1] = E.x;while (true) {//释放最小堆中的所有节点delete [] E.x;try {H.DeleteMin(E);}catch (OutOfBounds) {break;}}return bestc;}while 循环不断地展开E-节点,直到找到一个叶节点.当s = n - 1时即可说明找到了一个叶节点.旅行路径前缀是x [ 0 : n - 1 ],这个前缀中包含了有向图中所有的n个顶点.因此s = n - 1的活节点即为一个叶节点.由于算法本身的性质,在叶节点上lco st 和cc 恰好等于叶节点对应的旅行路径的耗费.由于所有剩余的活节点的lcost 值都大于等于从最小堆中取出的第一个叶节点的lcost 值,所以它们并不能帮助我们找到更好的叶节点,因此,当某个叶节点成为E-节点后,搜索过程即终止. while 循环体被分别按两种情况处理,一种是处理s = n - 2的E-节点,这时,E-节点是某个单独叶节点的父节点.如果这个叶节点对应的是一个可行的旅行路径,并且此旅行路径的耗费小于当前所能找到的最小耗费,则此叶节点被插入最小堆中,否则叶节点被删除,并开始处理下一个E-节点.其余的E-节点都放在while 循环的第二种情况中处理.首先,为每个E-节点生成它的两个子节点,由于每个E-节点代表着一条可行的路径x [ 0 : s ],因此当且仅当是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时,它的子节点可行.对于每个可行的孩子节点,将边的耗费加上 即可得到此孩子节点的路径前缀( x [ 0 : s ],x) 的耗费c c.由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边,因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和,因而可以把这个下限值作为E-节点所生成孩子的lcost 值.如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c,则把新生成的孩子加入活节点队列(即最小堆)中.如果有向图没有旅行路径,程序返回N o E d g e;否则,返回最优旅行路径的耗费,而最优旅行路径的顶点序列存储在数组v 中.3.回朔法解TSP问题回朔法有"通用解题法"之称,它采用深度优先方式系统地搜索问题的所有解,基本思路是:确定解空间的组织结构之后,从根结点出发,即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点,这个结点成为新的活结点,并成为当前扩展结点.如果在当前扩展结点处不能再向纵深方向转移,则当前扩展结点成为死结点.此时,回溯到最近的活结点处,并使其成为当前扩展结点,回溯到以这种工作方式递归地在解空间中搜索,直到找到所求解空间中已经无活结点为止.旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……, n的所有排列的递归算法Perm类似.设开始时x=[ 1,2,… n ],则相应的排列树由x[ 1:n ]的所有排列构成.旅行商问题的回溯算法找旅行商回路的回溯算法Backtrack是类Treveling的私有成员函数,TSP是Treveling的友员.TSP(v)返回旅行售货员回路最小费用.整型数组v返回相应的回路.如果所给的图G不含旅行售货员回路,则返回NoEdge.函数TSP所作的工作主要是为调用Backtrack所需要变量初始化.由TSP调用Backtrack(2)搜索整个解空间.在递归函数Backtrack中,当i = n时,当前扩展结点是排列树的叶结点的父结点.此时,算法检测图G是否存在一条从顶点x[ n-1 ]到顶点x[ n ]的边和一条从顶点x[ n ]到顶点1的边.如果这两条边都存在,则找一条旅行售货员回路.此时,算法还需判断这条回路的费用是否优于已找到的当前最优回路的费用best.如果是,则必须更新当前最优值bestc和当前最优解bestx.当i < n时,当前扩展结点位于排列树的第i–1 层.图G中存在从顶点x[ i-1 ]到顶点x[ i ]的边时,x[ 1:i ]构成图G的一条路径,且当x[ 1:i ]的费用小于当前最优值时,算法进入排列树的第I层.否则将剪去相应的子树.算法中用变量cc记录当前路径x[ 1:i ]的费用.解旅行商售货员问题的回溯法可描述如下:templateclass Traveling {friend Type TSP(int * *,int [],Type);private:void Backtrack(int i);int n, //图G的顶点数* x, //当前解*bestx; //当前最优解Type * *a, //图G的邻接矩阵cc, //当前费用bestc, //当前最优值NoEdge; //无边际记};templatevode Traveling::Backtrack(int i){if(I==n){if(a[x[n-1]][x[n]]! = NoEdge &&a[x[n]][1]!= NoEdge &&(cc + a[x[n-1]][x[n]]+a[x[n]][1]bestc== NoEdge) ){for(int j=1;j<=n;j++)bestx[j]=x[j];bestc =cc + a[x[n-1]][x[n]]+ a[x[n]][1];}}else {for(int j=I; j<=n;j++)//是否可进入x[j]子树if(a[x[i-1]][x[j]]! = NoEdge &&(cc + a[x[i-1]][x[i]]< bestc||bestc == NoEdge//搜索子数Swap(x[i],x[j]);cc += a[x[i-1]][x[i]];Backtrack(I+1);cc -= a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}templateType TSP(Type * *a,int v[],int n,Type NoEdge){Traveling Y;//初始化YY.x = new int[n+1];// 置x为单位排列for(int i=1;i<=n;i++)Y.x[i] = I;Y.a=a;Y.n=n;Y.bestc = NoEdge;Y.bestc = v; = 0;Y. NoEdge = NoEdge;//搜索x[2:n]的全排列Y.Backtrack(2);Delete[] Y.x;三.三种方法的比较1.动态规划法和回朔法的比较:这本来就是两个完全不同的领域,一个是算法领域,一个是数据结构问题.但两者又交叉,又有区别.从本质上讲就是算法与数据结构的本质区别,回朔是一个具体的算法,动态规划是数据结构中的一个概念.动态规划讲究的是状态的转化,以状态为基准,确定算法,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复.动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解.简单的说就是:动态规划法是从小单元开始积累计算结果.回朔讲究过程的推进与反还,随数据的搜索,标记,确定下一步的行进方向,回朔是去搜索.如果想要搜索时,发现有很多重复计算,就应该想到用动态规划了.动态规划和搜索都可以解决具有最优子结构的问题,然而动态规划在解决子问题的时候不重复计算已经计算过的子问题,对每个子问题只计算一次;而简单的搜索则递归地计算所有遇到的的子问题.比如一个问题的搜索树具有如下形式:........A......./.......B...C...../.\./.....D...E...F如果使用一般深度优先的搜索,依次搜索的顺序是A-B-D-E-C-E-F,注意其中节点E被重复搜索了两次;如果每个节点看作是一个子问题的话,节点E所代表的子问题就被重复计算了两次;但是如果是用动态规划,按照树的层次划分阶段,按照自底向上的顺序,则在第一阶段计算D,E,F;第二阶段计算B,C;第三阶段计算A;这样就没有重复计算子问题E.搜索法的优点是实现方便,缺点是在子问题有大量的重复的时候要重复计算子问题,效率较低;动态规划虽然效率高,但是阶段的划分和状态的表示比较复杂,另外,搜索的时候只要保存单前的结点;而动态规划则至少要保存上一个阶段的所有节点,比如在动态规划进行到第2阶段的时候,必须把第三阶段的D,E,F三个节点全部保存起来,所以动态规划是用空间换时间.另外,有一种折衷的办法,就是备忘录法,这是动态规划的一种变形.该方法的思想是:按照一般的搜索算法解决子问题,但是用一个表将所有解决过的子问题保存起来,遇到一个子问题的时候,先查表看是否是已经解决过的,如果已解决过了就不用重复计算.比如搜索上面那棵树,在A-B-D-E的时候,已经将E记录在表里了,等到了A-B-D-E-C的时候,发现E已经被搜索过,就不再搜索E,而直接搜索F,因此备忘录法的搜索顺序是A-B-D-E-C-(跳过E)-F自底向上的动态规划还有一个缺点,比如对于下面的树:........A......./.......B...C......G...../.\./.\..../.....D...E...F..H (I)如用自底向上的动态规划,各个阶段搜索的节点依次是:D,E,F,H,IB,C,GAA才是我们最终要解决的问题,可以看到,G,H,I根本与问题A无关,但是动态规划还是将它们也解决了一遍,这就造成了效率降低.而备忘录法则可以避免这种问题,按照备忘录法,搜索的次序仍然是:A-B-D-E-C-(跳过E)-F.备忘录法的优点是实现简单,且在子问题空间中存在大量冗余子问题的时候效率较高;但是要占用较大的内存空间(需要开一个很大的表来记录已经解决的子问题),而且如果用递归实现的话递归压栈出栈也会影响效率;而自底向上的动态规划一般用for循环就可以了.值得一提的是,用动态规划法来计算旅行商的时间复杂度是指数型的.2. 分支限界法和回朔法的比较:分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法.但在一般情况下,分支限界与回溯法的求解目标不同.回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解.我们先看一个列子:设G=(V,E)是一个带权图.图1中各边的费用(权)为一正数.图中的一条周游线是包括V中的每个顶点在内的一条回路.一条周游路线的费用是这条路线上所有边的费用之和.所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线.给定一个有n个顶点的带权图G,旅行售货员问题要找出图G的费用(权)最小的周游路线.图1是一个4顶点无向带权图.顶点序列1,2,4,3,1;1,3,2,4,1和1,4,3,2,1是该图中3条不同的周游路线. 301 256 1043 20 4图1 4顶点带权图该问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图G的一条周游路线.图1是当n=4时这种树结构的示例.其中从根结点A到叶结点L的路径上边的标号组成一条周游路线1,2,3,4,1.而从根结点到叶结点O的路径则表示周游路线1,3,4,2,1.图G的每一条周游路线都恰好对应解空间树中一条从根结点到叶结点的路径.因此,解空间树中叶结点个数为(n-1)!.A1B2 3 4C D E3 24 2 3F G H I J K4 3 4 2 3 2L M N O P Q图2 旅行售货员问题的解空间树对于图1中的图G,用回溯法找最小费用周游路线时,从解空间树的根结点A出发,搜索至B,C,F,L.在叶结点L处记录找到的周游路线1,2,3,4,1,该周游路线的费用为59.从叶结点L返回至最近活动结点F处.由于F处已没有可扩展结点,算法又返回到结点C处.结点C成为新扩展结点,由新扩展结点,算法再移至结点G 后又移至结点M,得到周游路线1,2,4,3,1,其费用为66.这个费用不比已有周游路线1,2,3,4,1的费用小.因此,舍弃该结点.算法有依次返回至结点G,C,B.从结点B,算法继续搜索至结点D,H,N.在叶结点N算法返回至结点H,D,然后再从结点D开始继续向纵深搜索至结点O.依次方式算法继续搜索遍整个解空间,最终得到1,3,2,4,1是一条最小费用周游路线.以上便是回溯法找最小费用周游路线的实列,但如果我们用分支限界法来解的话,会更适合.由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同.回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小消耗优先的方式搜索解空间树T.分支限界法的搜索策略是,在扩展结点处,先生成所有的儿子结点(分支),然后再从当前的活动点表中选择下一个扩展结点.为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上的最优解的分支推进,以便尽快的找出一个最优解.四.结论:参考文献:。

T S P问题分析动态规划-分支界限法-蛮力法算法综合实验报告学号： 1004111115 姓名：李宏强一、实验内容：分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。

二、程序设计的基本思想、原理和算法描述：（包括程序的数据结构、函数组成、输入/输出设计、符号名说明等）1、动态规划法(1)数据结构：①利用二进制来表示集合，则集合S可由一个十进制数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问题算法综述一、本文概述本文旨在全面综述求解旅行商问题（Traveling Salesman Problem, TSP）的各种算法。

TSP问题是一个经典的组合优化问题，自提出以来就引起了广泛的关注和研究。

该问题可以描述为：给定一系列城市和每对城市之间的距离，求解一条最短的可能路线，使得一个旅行商从某个城市出发，经过每个城市恰好一次，最后返回出发城市。

本文将首先介绍TSP问题的基本定义、性质及其在实际应用中的重要性。

接着，我们将综述传统的精确算法，如动态规划、分支定界法等，以及它们在求解TSP问题中的优缺点。

然后，我们将重点介绍启发式算法和元启发式算法，包括模拟退火、遗传算法、蚁群算法等，这些算法在求解大规模TSP问题时表现出良好的性能和效率。

本文还将探讨近年来新兴的机器学习算法在TSP问题求解中的应用，如深度学习、强化学习等。

我们将对各类算法进行总结和评价，分析它们在不同场景下的适用性和性能表现。

我们也将展望TSP问题求解算法的未来发展方向，以期为相关领域的研究和实践提供有益的参考和指导。

二、经典算法求解旅行商问题（TSP）的经典算法多种多样，每种算法都有其独特的优缺点和适用场景。

本节将对一些代表性的经典算法进行综述。

暴力穷举法（Brute-Force）：暴力穷举法是最简单直观的TSP求解算法。

其基本思想是生成所有可能的旅行路径，计算每条路径的总距离，然后选择最短的那条。

虽然这种方法在理论上可以找到最优解，但由于其时间复杂度为O(n!)，对于大规模问题来说计算量极大，因此并不实用。

动态规划（Dynamic Programming, DP）：动态规划是一种通过将问题分解为更小的子问题来求解的优化方法。

对于TSP问题，DP算法可以将一个大循环中的多个子问题合并成一个子问题，从而减少重复计算。

然而，TSP的DP算法仍面临“维度灾难”的问题，即当城市数量增多时，所需存储空间和计算时间呈指数级增长。