9、回溯法求解哈密尔顿回路

《9、回溯法求解哈密尔顿回路》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯法求解一般哈密顿尔回路数学与计算机学院课程设计说明书课程名称:算法设计与分析-课程设计课程代码:7106620题目:回溯法求解一般哈密尔顿回路年级/专业/班:学生姓名:学　　号:开始时间:2010年12月27日完成时间:2011年01月07日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日回溯法求解一般哈密顿尔回路目录1引言11.1问题的提出11.2任务与分析12算法12.1递归回溯法求解哈密顿尔回路算法12.2非递归回溯法求解哈密顿尔回路算

2、法23设计方案33.1整体设计方案33.2程序递归算法的主要代码33.3程序非递归算法的主要代码43.4程序的其他函数54系统测试64.1测试数据64.2程序的录入、编译和连接74.3运行程序74.4进入主界面84.4测试递归回溯法求解图的所有哈密顿尔回路84.5测试非递归回溯法求解图的所有哈密顿尔回路94.6测试第二组数据94.7测试退出模块10结论11致谢12参考文献13回溯法求解一般哈密顿尔回路摘要本次我的课程设计题目是“用回溯法求解一般哈密尔顿回路问题”，主要内容是给出用回溯法求解一般哈密尔顿回路问题的算法并编程实现。所

3、涉及到的知识是《算法设计与分析》中的回溯法，以及《图论》中的哈密顿尔回路。回溯法：从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。哈密顿回路：从某顶点开始，经过图G全部顶点一次回到起点的回路。关键词：回溯法哈密顿尔回路算法编程实现16回溯法求解一般哈密顿尔回路1引言1.1问题的提出我所做的课程设计就是用回溯法求解一般哈密尔顿回路问题，即从某顶点开始，经过图G全部顶点一次回到起点的回路。1.2任务与分析本课程设计主要的目的是：通过回溯的方法找出图的一般哈密顿尔回路，并且能够输出。题目分析：回溯法是一个既带有系统性

4、又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题

5、。哈密顿回路：从某顶点开始，经过图G全部顶点一次回到起点的回路。2算法2.1递归回溯法求解哈密顿尔回路算法2.1.1递归求图的所有哈密顿尔回路算法1）解向量用数组X[1...n]表示；X[k]=0无合法顶点；X数组初始化为0；2）若k=n时，需检查x[k]是否有边与x[1]相连（回到起点，构成回路）3）用k=1启动（指定哈密顿回路的起点）由此可得以下算法：statushamilton(intk)16回溯法求解一般哈密顿尔回路{if(k>n-1&&c[x[k-1]][0]==1){output(x);flag=1;}elsefor

6、(inti=k;i

7、法：1．将顶点数组x[n]初始化为0，标志数组visited[n]初始化为0；2．k=1;visited[1]=1;x[1]=1;从顶点1出发构造哈密顿回路；16回溯法求解一般哈密顿尔回路3．while(k>=1)3.1x[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否则，3

8、.4.1若数组x[n]构成哈密顿路径的部分解，则k=k+1，转步骤3；3.4.2否则，重置x[k]，k=k-1，取消顶点x[k]的访问标志，转步骤3；3设计方案3.1整体设计方案这两个算法是通过C++语言编程实现的，在主菜单栏可以分成三块：1、递归求图的所有哈密