用回溯法求解一般哈密尔顿回路问题

1用回溯法求解一般哈密尔顿回路问题目录引言........................................................-1-1需求分析..................................................-2-1.1问题的提出...........................................-2-1.2问题的描述...........................................-2-1.3算法的描述...........................................-3-2概要设计.................................................-4-2.1系统运行环境.........................................-4-2.2算法的实现...........................................-4-2.3接口设计............................................-12-2.4出错处理设计........................................-12-2.5维护设计............................................-13-3详细设计.................................................-14-3.1算法的分析..........................................-14-3.2程序的思路..........................................-15-3.3程序的实现..........................................-15-3.4设计环境............................................-19-4调试分析.................................................-20-4.1有哈密尔顿回路连通图................................-20-4.2无哈密尔顿回路连通图................................-22-5总结.....................................................-23-参考文献...................................................-25-附录.......................................................-26-2摘要回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法，该算法既带有系统性又带有跳跃性，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判定该节点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该节点为跟的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行探索。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法。回溯法可以用来求出问题的全部解，也可以在求出问题的一个解之后停止对问题的求解，即只求该问题是否有解。它适用于解一些组合数较大的问题。哈密尔顿回路路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径。本文主要讲的就是用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题，并用具体的算法来实现它。关键词：回溯法哈密尔顿回路空间树-1-用回溯法求解一般哈密尔顿回路问题引言回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树[1]。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束[2]。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。-2-用回溯法求解一般哈密尔顿回路问题1需求分析1.1问题的提出在求解一些问题（如走迷宫、地图着色等问题）时，题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能的决策方案；由于没有固定、明确的数学解析方法，往往要采用搜索的做法，即从某一个初始状态出发，不断地向前（即下一个状态）搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点（如在缺乏全局及足够的前瞻信息的情况下进行搜索等）[3]，会导致走到某一状态就走不下去的情况，这时，就必须回头（即回到上一步，而不是回到最初的状态），再尝试其他的可能性，换一个方向或方法再试试。这样，不断地向前探索、回溯，再向前、再回溯，直至最终得出问题的解，或者一路回溯到出发点（出现这种情况即表示原问题无解）[4]。注意，这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径，而是采用深度优先的方式，沿着一条路径，尽可能深入地向前探索。1.2问题的描述1．设计内容：给出内存分类法的多种应用，给出这些应用对应的算法并编程实现。2．设计要求：(1)给出各种分类法的求解算法;(2)编程实现各种分类法的算法;(3)对所写的每个算法给出时空复杂性分析。-3-用回溯法求解一般哈密尔顿回路问题1.3算法的描述该算法讲的就是用回溯法求解一个无向图中是否存在哈密尔顿回路的问题。所谓哈密尔顿回路就是指经过图（有向图或无向图）中所有顶点一次且仅一次的通路。用回溯法解哈密尔顿回路问题首先要画出问题的解空间树，该解空间树是一棵最大度是n的树（其中n为图中的顶点数），树中只有第一个结点的度是n，其余结点的度都为n-1（该结点不用与其自身相连）。在编写算法时可以通过判断该边在图的邻接矩阵中的值来剪枝，如果其值不是1则说明该边不存在则剪枝不用搜索。由于在求图的哈密尔顿回路时走过的顶点不能再重复走，所以要对已经遍历过的顶点做一个标记，如果在搜索时找到的是一个带有标记的顶点，那么该路径也是不可行的，应剪去。-4-用回溯法求解一般哈密尔顿回路问题2概要设计此算法设计为用回溯法求解一般哈密尔顿回路问题，设计的主要内容为：给出内存分类法的多种应用，给出各类分类法的求解算法，编程实现各种分类法的算法，对所写的每一个算法给出时间空间复杂性分析。2.1系统运行环境根据目前市场上能够提供的硬件。我们设计系统的硬件环境如下：IBMPC286及以上档次微机、便携机、各种品牌兼容机，最佳档次为386以上微机。512M或512M以上内存，最好具备扩展内存EGA、VGA、TVGA、所有SUPERVGA彩色显示器。20M以上硬盘。任何光电鼠或机械鼠。软件环境如下：MS（PC）DOS3.3或以上版本；采用VC++进行开发；2.2算法的实现1.个体类classCind{public:int&operator[](intindex){returndata[index];}Cind&Cind::operator=(Cind&a);booloperator==(Cind&ind);voidCrossWith(Cind&a);voidMut();voidshow();voidSetArc();doublefun();Cind();virtual~Cind();int*data;staticintn;-5-用回溯法求解一般哈密尔顿回路问题doublefitness;};//ind.cpp:implementationoftheCindclass.///////////////////////////////////////////////////////////////////#includestdafx.h#includeGrWndapp.h#includeshapelist.h#includeind.h#includenode.h#includearc.h#includemath.h#ifdef_DEBUG#undefTHIS_FILEstaticcharTHIS_FILE[]=__FILE__;#definenewDEBUG_NEW#endifintCind::n;externCShapeListnode_list,arc_list;//Construction/DestructionCind::Cind(){data=newint[n];bool*flag=newbool[n];for(inti=0;in;i++)flag=true;intk=0;for(intm=n;m0;m--){intt=rand()%m;intj=0;for(i=0;in;i++)if(flag){if(j==t){data[k++]=i;flag=false;break;-6-用回溯法求解一般哈密尔顿回路问题}j++;}}delete[]flag;}Cind::~Cind(){delete[]data;}doubleCind::fun(){doublev=0;CNode*pn1,*pn2;for(inti=0;in-1;i++){pn1=(CNode*)node_list.GetShape(data);pn2=(CNode*)node_list.GetShape(data[i+1]);v+=sqrt((pn1-x-pn2-x)*(pn1-x-pn2-x)+(pn1-y-pn2-y)*(pn1-y-pn2-y));}pn1=(CNode*)node_list.GetShape(data[0]);v+=sqrt((pn1-x-pn2-x)*(pn1-x-pn2-x)+(pn1-y-pn2-y)*(pn1-y-pn2-y));returnv;}voidCind::SetArc(){arc_list.Clear();CArc*parc;for(inti=0;in-1;i++){parc=newCArc((CNode*)node_list.GetShape(data),(CNode*)node_list.GetShape(data[i+1]));arc_list.Add(parc);}-7-用回溯法求解一般哈密尔顿回路问题parc=newCArc((CNode*)node_list.GetShape(data),(CNode*)node_list.GetShape(data[0]));arc_list.Add(parc);}voidCind::show(){TRACE(Theind:\n);for(inti=0;in;i++)TRACE(%d-,data);TRACE(\n);}voidCind::Mut(){intp1=rand()%n;intp2=rand()%n;intt=data[p1];data[p1]=data[p2];data[p2]=t;}voidCind::CrossWith(Cind&a){intpos=rand()%(n-1);pos++;int*t1,*t2;t1=newint[n];t2=newint[n];intk=0;for(inti=0;in;i++){for(intj=0;jpos;j++){if(data==a[j])break;}if(j==pos)//findno