动态规划法,回溯法,分支限界法求解TSP问题实验报告

动态规划法,回溯法,分支限界法求解TSP问题实验报告TSP问题算法实验报告指导教师：季晓慧姓名：辛瑞乾学号： 1004131114 提交日期： 2015年11月目录总述 2 动态规划法 2 算法问题分析 2 算法设计 2 实现代码 2 输入输出截图 5 OJ提交截图 5 算法优化分析 5 回溯法 5 算法问题分析 5 算法设计 6 实现代码 6 输入输出截图 8 OJ提交截图 8 算法优化分析 9 ...

TSP问题算法实验报告指导教师：季晓慧姓名：辛瑞乾学号： 1004131114 提交日期： 2015年11月目录总述 2 动态规划法 2 算法问题分析 2 算法设计 2 实现代码 2 输入输出截图 5 OJ提交截图 5 算法优化分析 5 回溯法 5 算法问题分析 5 算法设计 6 实现代码 6 输入输出截图 8 OJ提交截图 8 算法优化分析 9 分支限界法 9 算法问题分析 9 算法设计 9 实现代码 9 输入输出截图 14 OJ提交截图 14 算法优化分析 14 总结 15 总述 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug "output for debug\n" #define pi (acos(-1.0)) #define eps (1e-8) #define inf 0x3f3f3f3f #define ll long longint #define lsonl , m , rt<< 1 #define rson m + 1 , r , rt<< 1 | 1 using namespace std; constint mod = 1000000007; constint Max = 100005; intn,mp[20][20],dp[20][40000]; int main() { while(~scanf("%d",&n)) { intans=inf; memset(mp,0,sizeof mp); for(inti=0; i0){ x=dp[k][(j-(1<<(k-1)))]+mp[i][k]; y=min(y,x); } } dp[i][j]=y; } } } dp[0][mx-1]=inf; for(inti=1;i 标志初始化为0，然后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。采用邻接矩阵mp[n][n]存储顶点之间边的情况，为避免在函数间传递参数，将数组mp设置为全局变量，设数组x[n]表示哈密顿回路经过的顶点。算法设计输入:无向图G=(V,E) 输出：哈密顿回路 1、将顶点数组x[n]初始化为0，标志数组vis[n]初始化为0； 2、从顶点0出发构造哈密顿回路：vis[0]=1;x[0]=1;k=1; 3、 While(k>=1) 3.1、x[k]=x[k]+1，搜索下一个顶点。 3.2、若n个顶点没有被穷举完，则执行下列操作 3.2.1、若顶点x[k]不在湖密顿回路上并且(x[k-1],x[k])∈E，转步骤3.3； 3.2.2、否则，x[k]=x[k]+1,搜索下一个顶点。 3.3、若数组x[n]已经形成哈密顿路径，则输出数组x[n]，算法结束； 3.4、若数组x[n]构成哈密顿路径的部分解，则k=k+1，转步骤3； 3.5、否则，取消顶点x[k]的访问标志，重置x[k],k=k-1，转步骤3。实现代码 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug "output for debug\n" #define pi (acos(-1.0)) #define eps (1e-8) #define inf 0x3f3f3f3f #define ll long longint

                    本文档为【动态规划法,回溯法,分支限界法求解TSP问题实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

动态规划法,回溯法,分支限界法求解TSP问题实验报告

你可能还喜欢