《用回溯法求解一般哈密尔顿回路问题》由会员分享，可在线阅读，更多相关《用回溯法求解一般哈密尔顿回路问题（29页珍藏版）》请在金锄头文库上搜索。
1、1用回溯法求解一般哈密尔顿回路问题目 录 引言 .- 1 -1 1 需求分析需求分析 .- 2 -1.11.1 问题的提出问题的提出 .- 2 -1.21.2 问题的描述问题的描述 .- 2 -1.31.3 算法的描述算法的描述 .- 3 -2 2 概要设计概要设计 .- 4 -2.12.1 系统运行环境系统运行环境 .- 4 -2.22.2 算法的实现算法的实现 .- 4 -2.32.3 接口设计接口设计 .- 12 -2.42.4 出错处理设计出错处理设计 .- 12 -2.52.5 维护设计维护设计 .- 13 -3 3 详细设计详细设计 .- 14 -3.13.1 算法的分析算法的分析
2、 .- 14 -3.23.2 程序的思路程序的思路 .- 15 -3.33.3 程序的实现程序的实现 .- 15 -3.43.4 设计环境设计环境 .- 19 -4 4 调试分析调试分析 .- 20 -4.14.1 有哈密尔顿回路连通图有哈密尔顿回路连通图 .- 20 -4.24.2 无哈密尔顿回路连通图无哈密尔顿回路连通图 .- 22 -5 5 总结总结 .- 23 -参考文献参考文献 .- 25 -附录附录 .- 26 -2摘摘 要要 回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法，该算法既带有系统性又带有跳跃性，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点
3、出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判定该节点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该节点为跟的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行探索。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法。回溯法可以用来求出问题的全部解，也可以在求出问题的一个解之后停止对问题的求解，即只求该问题是否有解。它适用于解一些组合数较大的问题。哈密尔顿回路路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径。本文主要讲的就是用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题，并用具体的算法来实现它。 关键词：回溯法 哈密尔顿回路
4、 空间树 - 1 -用回溯法求解一般哈密尔顿回路问题引言回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树1。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束 2。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解
5、一些组合数较大的问题。 - 2 -用回溯法求解一般哈密尔顿回路问题1 1 需求分析需求分析1.11.1 问题的提出问题的提出 在求解一些问题（如走迷宫、地图着色等问题）时，题目的要求 可能是求出原问题的一种或所有可能的解决方案。这类问题的解往 往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能 的决策方案；由于没有固定、明确的数学解析方法，往往要采用搜 索的做法，即从某一个初始状态出发，不断地向前（即下一个状态） 搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的 解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点 （如在缺乏全局及足够的前瞻信息的情况下进行搜索等）3，会
6、导 致走到某一状态就走不下去的情况，这时，就必须回头（即回到上 一步，而不是回到最初的状态） ，再尝试其 他的可能性，换一个方 向或方法再试试。这样，不断地向前探索、回溯，再向前、再回溯， 直至最终得出问题的解，或者一路回溯到出发点（出现这种情况即 表示原问题无解）4 。注意，这种搜索过程并不是尝试搜索问题 解空间中所有的可能状态和路径，而是采用深度优先的方式，沿着 一条路径，尽可能深入地向前探索。1.21.2 问题的描述问题的描述1设计内容：给出内存分类法的多种应用，给出这些应用对应的算法并编程实 现。2设计要求：(1)给出各种分类法的求解算法;(2)编程实现各种分类法的算法;(3)对所写的
7、每个算法给出时空复杂性分析。- 3 -用回溯法求解一般哈密尔顿回路问题1.31.3 算法的描述算法的描述 该算法讲的就是用回溯法求解一个无向图中是否存在哈密尔顿 回路的问题。所谓哈密尔顿回路就是指经过图（有向图或无向图） 中所有顶点一次且仅一次的通路。用回溯法解哈密尔顿回路问题首 先要画出问题的解空间树，该解空间树是一棵最大度是 n 的树（其 中 n 为图中的顶点数） ，树中只有第一个结点的度是 n，其余结点 的度都为 n-1（该结点不用与其自身相连） 。在编写算法时可以通过 判断该边在图的邻接矩阵中的值来剪枝，如果其值不是 1 则说明该 边不存在则剪枝不用搜索。由于在求图的哈密尔顿回路时走过
8、的顶 点不能再重复走，所以要对已经遍历过的顶点做一个标记，如果在 搜索时找到的是一个带有标记的顶点，那么该路径也是不可行的， 应剪去。- 4 -用回溯法求解一般哈密尔顿回路问题2 2 概要设计概要设计 此算法设计为用回溯法求解一般哈密尔顿回路问题，设计的主要 内容为：给出内存分类法的多种应用，给出各类分类法的求解算法， 编程实现各种分类法的算法，对所写的每一个算法给出时间空间复 杂性分析。2.12.1 系统运行环境系统运行环境根据目前市场上能够提供的硬件。我们设计系统的硬件环境如下： IBM PC286 及以上档次微机、便携机、各种品牌兼容机，最 佳档次为 386 以上微机。 512M 或 5
9、12M 以上内存，最好具备扩展内存 EGA、VGA、TVGA、所有 SUPERVGA 彩色显示器。 20M 以上硬盘。 任何光电鼠或机械鼠。 软件环境如下： MS（PC）DOS3.3 或以上版本；采用 VC+进行开发；2.2.2 2 算法的实现算法的实现1.1.个体类个体类class Cind public: int Cind bool operator = (Cind void CrossWith(Cind void Mut(); void show(); void SetArc(); double fun(); Cind(); virtual Cind(); int * data;- 5
10、-用回溯法求解一般哈密尔顿回路问题static int n; double fitness; ; / ind.cpp: implementation of the Cind class. / / #include “stdafx.h“ #include “GrWndapp.h“ #include “shapelist.h“ #include “ind.h“ #include “node.h“ #include “arc.h“ #include “math.h“#ifdef _DEBUG #undef THIS_FILE static char THIS_FILE=_FILE_; #define
11、 new DEBUG_NEW #endif int Cind:n; extern CShapeList node_list,arc_list; / Construction/Destruction Cind:Cind() data = new intn; bool * flag = new booln;for ( int i=0; i0; m- ) int t = rand()%m; int j = 0;for ( i = 0; ix - pn2-x)*(pn1-x - pn2-x)+ (pn1-y-pn2-y)*(pn1-y-pn2-y); pn1 = (CNode *)node_list.
12、GetShape(data0); v += sqrt(pn1-x - pn2-x)*(pn1-x - pn2-x)+ (pn1-y-pn2-y)*(pn1-y-pn2-y);return v; void Cind:SetArc() arc_list.Clear(); CArc * parc; for ( int i=0; i“,data ); TRACE(“n“); void Cind:Mut() int p1 = rand() % n; int p2 = rand() % n; int t = datap1; datap1=datap2; datap2=t; void Cind:CrossWith(Cind pos +;int * t1, * t2; t1 = new intn; t2 = new intn;int k=0; for ( int i=0; i groupj+1.fitness ) t=groupj; groupj=groupj+1; groupj+1=t; 2.32.3 接口设计接口设计1.外部接口 (1) 用户界面 采用图形用户界面（GUI） ，包含菜单、按钮、对话框等元素。 (2) 软件接口 软件运行于 windows XP 极
