哈密顿回路课程实验报告

实用文档《算法分析与设计》课程设计报告题目：哈密顿回路专业：计算机科学与技术班级：14计算机科学与技术二班姓名：陈凌志洪文豪杨旭指导教师：湛维明2016年5月22日河北金融学院课程设计报告目录一、问题描述 3二、问题分析与解题思路 31．确定解题方法 32．用回溯法分析和解哈密顿回路问题 33.由以上解题思路作出基本思路图： 4三、由基本思路图编写算法并实现可视化 51、源代码 52、算法实现图 7四、关于本次算法实验的总结 8一、问题描述哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过的所有其他节点且只经过一次。从一张普通图中的任意一点出发，路途中经过图中每一个结点当且仅当一次的回路，称为为哈密顿回路。要求：随机生成无向图，且图中部分顶点间无通路。设计算法找到一条哈密顿回路。如果实现可视化展示给予大幅度额外加分。要满足两个条件：封闭的环，是一个连通图，且图中任意两点可达。二、问题分析与解题思路1．确定解题方法由于哈密顿回路问题是一个完全NP问题，没有多项式可解，所以我们用最简单的回溯法找出哈密顿回路，并且能够实现可视化输出。回溯法的基本思路：回溯法是有系统性和跳跃性的搜算算法。它在包含的问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜算至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种算法比较适合哈密顿回路问题。

2．用回溯法分析和解哈密顿回路问题在求解哈密顿问题时，题目要求是求出一种可行的路径，所以这个问题的解可能是由很多很多步骤构成的，每一步可能还有不同的决策方向。是一个完全NP问题，没有固定明确的数学解析方法。所以我们要用搜素的方法，从某一个初始状态下出发，不断的向下一个状态搜索，以达到想要达到的最终目的，来得到我们想要的解。在搜索的过程中，由于这个图本身的特点，会有走到某一个状态就走不下去的时候，这个时候，我们就必须往回走，即回到上一步，再尝试别的可能性，别的方向或路径。这样不断的向前走，回溯，再向前，再回溯……直到最终得到解，或者由于原问题无解而一路回溯到出发点。在回溯法的搜索中要注意的是，我们并不需要尝试搜索问题解空间里的所有可能方向和路径，而是以深度优先搜素的方式，沿着一条路径尽可能的向前探索。哈密顿回路问题的解空间是一颗最大度为n的树（n为原图中的顶点数）。且该树中只有第一个结点度为n，其余的结点都为n-1（因为它不必与自身相连）。在回溯法编写代码解决哈密顿问题的时候，我们需要判断路能不能走，有没有走过和有没有这条路，所以我们用到字典。由于路在生成的时候没有的路我们根本没有生成，所以我们考虑顶点有没有走过，将已经走过的顶点写进字典，再搜素的时候如果遇到字典里面的顶点，说明已经走过，此路不可行。初始化点和路3.由以上解题思路作出基本思路图：初始化点和路判断是否走判断是否走完所有顶点否路径变红路径变红是判断最后一个点到第一个点是否为通路判断最后一个点到第一个点是否为通路输出图像输出图像走另一个点走另一个点否判断下一个点是否走过判断下一个点是否走过返回上一个点否返回上一个点继续往前走是继续往前走三、由基本思路图编写算法并实现可视化1、源代码#-*-coding:utf8-*-importnetworkxasnximportmatplotlib.pyplotaspltimportrandom首先确定顶点的数量，路程长度初始化（用来记录是否走完了所有点），记录有几条通路，点的标签（给各个顶点一个编号便于使用）和点的判断条件（用0表示没有走过。1表示已经走过）等基本条件。n=6#en=0#路程长度count1=0#记录有几条通路dot=[aforainrange(1,n+1)]#点的标签dotJudgement=[1forainrange(1,n+1)]#点的判断条件随机按照50%的概率生成顶点间的路。edge=[]#边forxinrange(1,n+1):foryinrange(x,n+1):if(random.randint(1,10)<=5)&(x!=y):#按照50%的概率构建路edge.append((x,y))count1+=1根据先前的问题分析描述生成字典。（为了更清楚的可视化，我们用红色标记出回路。）judgement=[1forzinrange(1,count1+1)]#判断这条路是否走过colours=["b"forcinrange(1,count1+1)]#边的颜色A={key:valforval,keyinzip(judgement,edge)}#把边和判断条件（是否走过）合成一个字典B={key:valforval,keyinzip(dotJudgement,dot)}#把点和判断条件（是否走过）合成一个字典C={key:valforval,keyinzip(colours,edge)}#把边和对应颜色合成一个字典准备工作写完。核心算法如下：defHamilton(dot1,len1):a=dot1#记录点if(len1==n-1):#如果路程走到尽头if((1,dot1)inA.keys()):#判断这个点到起点有没有通路if(A[(1,dot1)]==1):#判断这条路有没有走过C[(1,dot1)]="r"#有则把路改为红色returnTrueelse:returnFalseforcountinrange(2,n+1):if((dot1,count)inA):#判断字典中是否有这个键if(B[count]==1):#如果这条路没走过，且点没走过B[count]=0#标记点走过len1+=1#路程加一C[(dot1,count)]="r"#把路变为红色if(Hamilton(count,len1)):#递归，找到后直接returnreturnTruelen1-=1#没找到则退回去B[count]=1#退回C[(dot1,count)]="b"#颜色改为蓝色dot1=a#点也退回if((count,dot1)inA):#判断字典中是否有这个键，字典生成的时候是小数在前，所以多一个if判断，才能遍历所有路径if((B[count]==1)):#如果这条路没走过，且点没走过B[count]=0#标记点走过len1+=1#路程加一C[(count,dot1)]="r"#把路变为红色#dot1=count#换点if(Hamilton(count,len1)):#递归，找到后直接returnreturnTruelen1-=1#没找到则退回去B[count]=1#退回C[(count,dot1)]="b"#颜色改为蓝色dot1=a#点也退回returnFalse完成可视化：defshow():G=nx.Graph()G.add_edges_from(edges)pos=nx.circular_layout(G)nx.draw_networkx_nodes(G,pos,node_size=200)nx.draw_networkx_edges(G,pos,edge_color=colour,width=3)plt.show()if(Hamilton(1,len)):edges=[eforeinC.keys()]colour=[]foryinedge:if(C[y]=="r"):colour.append("r")if(C[y]=="b"):colour.append("b")show()else:print("没有哈密顿回路")G=nx.Graph()G.add_edges_from(edge)pos=nx.circular_layout(G)nx.draw_networkx_nodes(G,pos,node_size=200)nx.draw_networkx_edges(G,pos,width=2)plt.show()最后的运行结果图如下（我们自定义的六个顶点，并给出了像最后一张图那样没有形成哈密顿回路的例子）2、算法实现图四、关于本次算法实验的总结回溯法，即在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束的方法。回溯法的一般解题步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪