回溯法求哈密尔顿回路试验报告.doc

《回溯法求哈密尔顿回路试验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、回溯法求哈密尔顿回路2014211053谭富林一.实验目的和算法分析试验目的：通过回溯的方法找出图的一般哈密顿尔回路，并且能够输出结果。算法分析：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树

2、都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。哈密顿回路是从某顶点开始，经过图全部顶点一次回到起点的回路。二.实验内容1.编写实现算法：给定n点，m条变，找出所有哈密尔顿回路。2.将输出数据显示在控制台窗体中。3.对实验结果进行分析。三.实验开发工具操作系统：windows8开发工具:Microsoftvisualstudio2010开发语言:C++四.实验操作程序的思路：创建一个N节点的连通图输入顶

3、点N的值输入连通图的边数创建每一条边，构成完整连通图求出哈密尔顿回路的所有解程序的实现：#include#include#include//全局变量声明intm=1;//用于标志哈密尔顿回路的总个数intn;//intx[128];intgraph[128][128];voidnextvalue(intk){intj;while(1){x[k]=(x[k]+1)%(n+1);if(x[k]==0)return;if(graph[x[k-1]][x[k]]){for(j=1

4、;j<=k-1;j++){if(x[j]==x[k])break;}if(j==k){if(k

5、

6、(k==n&&graph[x[n]][1]))return;}}}}voidprint(intx[],intn){inti=1;printf("回路%d:",m);for(;i<=n;i++)printf("%d",x[i]);printf("");m++;}voidhamiltonian(intk){while(1){nextvalue(k);if(x[k]==0)return;if(k==n)print(x,n);el

7、sehamiltonian(k+1);}}voidmain(){inti,j,e,a,b;printf("***********哈密顿回路递归回溯算法***********");printf("********************************************");printf("请先创建一个n结点的连通图graph[n][n]");printf("请输入顶点n的值:");scanf_s("%d",&n);printf("图中一共有几条边？请输入以便我们创建图:");scanf_s("%d",

8、&e);for(i=1;i<=n;i++)for(j=1;j<=n;j++)graph[i][j]=0;for(i=1;i<=e;i++){printf("创建第%d条边:",i);printf("构成此边的一个顶点号(1~%d):",n);scanf_s("%d",&a);printf("另一个顶点号(1~%d):",n);scanf_s("%d",&b);graph[a][b]=graph[b][a]=1;}x[1]=1;for(i=2;i<=n;i++)x[i]=0;printf("以下为所求hamilton

9、ian回路的所有解");hamiltonian(2);}五．实验结果以及分析有哈密尔顿回路连通图：运行结果：无哈密尔顿回路连通图：六.总结通过本次课程设计，本人对算法设计与分析基础有了更深的认识，基本掌握了回溯法求解一般哈密尔顿回路的算法思路以及编程原理，提高了程序开发的能力，让能切实体会到算法在编程过程中的指导作用。通过课程设计，学会了按课程设计的任务要求完成各项程序的开发，对提高自身编程能力和项目管理能力有重要的现实意义。