《最长简单回路问题.docx》由会员分享，可在线阅读，更多相关《最长简单回路问题.docx（36页珍藏版）》请在三一办公上搜索。
1、关键词:最长简单回路问题摘要ABSTRACTKey words:目录1绪论11.1课题背景及目的11.2课题研究方法11.2.1基本内容11.2.2基本概念21.2.3算法设计22回溯法的介绍 42.1回溯法的概念42.1.1基本思想 42.1.2 一般表达 42.1.3 规律42.1.4空间树52.2回溯法的算法思想52.2.1回溯法的一般步骤52.2.2回溯法C语言举例63圆排列问题83.1圆排列问题描述 83.2算法设计83.2.1程序及思想93.2.2与圆排列随机算法的比较143.3 算法效率164测试数据及运行结果185调试心得19参考文献20附录211绪论1.1课程背景及目的算法设
2、计与分析主要取材于算法设计与分析领域的经典内容，并介绍了算法设计的 发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、 回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启 发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新 的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证 明以及NP完全理论等方面的内容。1.2课题研究方法设计出高质量的算法，并研究算法所耗费的计算资源与问题规模之间的函数关系。 算法设计与算法分析是不可分割的一个整体。算法分析的对象是被设计出的算法，而每 一个被设计出的算
3、法只有经过算法分析，才能评价其质量之优劣。计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂，计算量越来 越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题， 这就产生了理论可计算而现实不可计算的矛盾。20世纪60年代以来，随着各个领域算 法研究工作的发展，产生了一个崭新的研究领域，这就是算法的设计与分析。在这一方 面已取巨大的进展，它的研究成果对于计算机在各个领域的应用起着重要的作用。1.2.1基本内容按照算法所处理的对象进行分类，算法设计与分析主要有数值算法和非数值算法两 大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值 计算
4、的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、 模式匹配等有关非数值计算的算法问题。按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为确定型算法、 非确定型算法、交错型算法、随机型算法等（见计算复杂性理论）。另外，还有关于近似算法的研究。对于已经证明不存在快速算法，或者至今还未找第1页共29页到快速算法的问题，例如NP完全问题（见NP完全性），与其花费大量的时间去寻找精 确解，不如花费少量的时间去寻找近似解。1.2.2基本概念设计算法与分析算法的复杂度，都与计算模型有关，大多属于随机存取机器模型， 这是一种确定型的串行计算模型。随机存取机器是一种理想的计算机
5、，由一个累加器、一个存储器和一个程序组成。 存储器具有无限多个寄存器，每个寄存器可以存放任意大的一个自然数。程序是由一些 最基本的指令所组成的序列，这些指令通常是指包括直接寻址与间接寻址在内的加、减、 乘、除、取数、存数、条件转移和停机。所有的运算和逻辑判断都在累加器中进行。问题的大小，也称问题的规模，通常用一个自然数作为随机存取机器输入数据量多 少的度量。时间复杂度和空间复杂度分别表示对于规模为n的输入问题、随机存取机器所耗 费的时间与空间，它们都是n的函数。常用的时间和空间的度量方式是均匀耗费标准: 执行一条指令算作耗费一个单位的空间，使用一个寄存器算作耗费一个单位的空间；另 一种度量方式
6、是对数耗费标准（见随机存取机器模型）。复杂度函数的计算方式又有两 种：规模为n的所有问题的复杂度的最大值称为最环情况复杂度；规模为n的所有问题 的复杂度的平均值称为平均情况复杂度。当规模n增加时，复杂度的量级即极限属性称 为渐近复杂度。由于理论计算机与现实计算机之间的差异，以及不同的现实计算机之是 的差异，也由于算法设计与分析主要关心规模n比较大的情况，通常讨论的是渐近复 杂度。1.2.3算法设计算法设计的任务是对各类具体的问题设计高质量的算法，以及研究设计算法的一般 规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。（1）分治法把一个大规模问题划分成几个子问题，对每一个
7、子问题采用同样的处理方法，求出 各子问题的解答，再把这些子问题的解答组合成整个问题的解答。（2）动态规划当整个问题的解答无法由少数几个子问题的解答组合得出，而依赖于大量子问题的 解答，并且子问题的解答又需要反复利用多次时，系统地列表记录各个子问题的解答， 据此求出整个问题的解答。（3）贪婪法在算法的每一步骤，都采取当前看来可行的或最优的策略。这是一种最直接的方法， 只有在一些特殊情况下，贪婪法才能求出问题的解答。对于录求最优解的问题、贪婪法 通常只能求出近似解。（4）回溯法和分叉截断法为了寻求问题的解答，有时需要在所有的可能性（称为候选对象）中进行系统的搜 索，例如在寻求最优解的问题中，就常碰
8、到这种情况。这时，须把各种候选对象组织成 一棵树，每个树叶对应着一个候选对象，于是每个内部顶点就表示若十个候选对象（即在 此顶点下面的树叶）。回溯法是从树根开始按深度优先搜索的原则向下搜索，即沿着一个 方向尽量向下搜索，直到发现此方向上不可能存在解答时，就退到上一个顶点，沿另一 个方向进行同样的工作。分叉截断法也是从树根开始向下搜索，不同的是，分叉截断法 常常利用一个适当选取的评估函数，来决定应该从哪一点开始下一步搜索（分叉），以 及哪一点下方不可能存在解答，从而这点的下方不必进行搜索（截断）。评估函数选得 好，就会很快地找到解答，选得不好，就可能找不到解答或者找到的不是最优解（有时 它可以作
9、为最优解的一个近似解）。（5）算法分析对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算 法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以 为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧，针对不同的算法， 采用不同的分析方法。讨论某些问题类在一定的计算模型中的任意算法的复杂度至少是多大，也是算法分 析的一个内容，这就是下界问题。通常认为，多项式复杂度的算法是现实可行的，而指数复杂度的算法是现实不可行 的。2 NP完全性理论的介绍2.1 NP完全性理论2.1.1基本概念一般来说，把可由多项式时间算法求解的问题看作易处理问题，而将未能
10、找到多项 式时间算法求解的问题视作难处理问题。而这种所谓的难处理问题我们称之为NP难 度或NP完全问题。这类问题有一个共同特征：一个NP完全问题可以在多项式时间求解，当且仅当所 有其他NP完全问题都可以在多项式时间求解。如果任意一个NP难度问题存在一个多项 式时间算法，那么，所有NP完全问题都可以有多项式时间算法。在研究NP完全理论时，通常很容易重述一个问题使其解只有两个结论：yes或no。 这种情况下，称问题为判定问题。与此相对照，最优化问题是关心某个量的最大化或最 小化的问题。下面描述了怎样转化为这两类问题。例如：设S是一个实数序列，ELEMENT UNIQUENESS问题为，是否S中的所
11、有的数都 是不同的。判定问题：ELEMENT UNIQUENESS输入：一个整数序列S输出：在S中存在两个相等的元素吗最优问题：ELEMENT COUNT输入：一个整数序列S输 出：一个在S中频度最高的元素2.1.2基本分类（1）P 类定义1设A是求解问题II的一个算法，如果在展示问题II的一个实例时，在整 个执行过程中每一步都只有一种选择，则称A是确定性算法。因此如果对于同样的输入， 实例一遍又一遍的执行，它的输入从不改变。定义2判定问题的P类由这样的判定问题组成，它们的yes/no解可以用确定性 算法在运行多项式步数内。例如：排序问题：给出一个n个整数的表，它们是否按非降序排列？不相交集问
12、题：给出两个整数集合，它们的交集是否为空？(2) NP 类NP由这样的问题II组成，对于这些问题存在一个确定性算法A，该算法在对II的 一个实例展示一个断言解时，它能在多项式时间内验证解的正确性。即如果断言解导致 答案是yes，就存在一中方法可以在多项式时间内验证这个解。为了较形式的定义这个类，必须首先定义不确定性算法的概念.对于输入x, 一个 不确定性算法由下列两个阶段组成：(a) 猜测阶段：在这个阶段产生一个任意字符串y，它可能对应于输入实例的一个 解，也可以不对应解。(O(ni)(b) 验证阶段：在这个阶段，一个确定性算法验证两件事。首先，它检查产生的解 串y是否有合适的形式，如果不是，
13、则算法停下来并回答no；另一方面，如果y是合适 形式，那么算法继续检查它是否是问题实例x的解，如果确实是，那么它停下来且回答 yes，否则回答no。我们也要求这个阶段在多项式步数内完成。(O(nj)对于一个(不确定性)算法的运行时间，它仅仅是两个运行时间的和：一个是猜测 阶段的时间，另一个是验证阶段的时间。因此它是O(n】)+O(nj)=O(m)，k是某个非负整 数。定义3判定问题类NP由这样的判定问题组成：对于它们存在着多项式时间内运 行的不确定性算法。类P和NP之间，有下面的不同点：(a) P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或 解出；(b) NP是一个判定问
14、题类，这些问题可以用一个确定性算法在多项式时间内检查或 验证它们的解。(3) NP完全问题术语NP完全表示NP中判定问题的一个子类，它们在下述意义上是最难的，即如 果它们中的一个被证明用多项式时间确定算法可解，那么NP中的所有问题用多项式时 间确定性算法可解，即NP二P。定义4设II和II1是两个判定问题。如果存在一个确定性算法A，它的行为如下： 当给A展示问题II的一个实例I时，算法A可以把它变换为问题II1的实例I1，使得当 第5页共29页且仅当I1回答yes时，对I回答yes。而且，这个变换必须在多项式时间内完成。那么 我们说II多项式时间归约到II1，用符号11江poly 1表示。定义
15、5 一个判定问题II称为是NP困难的，如果对于NP中的每一个问题II1，。定义6 一个判定问题II称为是NP完全的，如果下列两个条件同时成立：(a) II 在 NP 中；(b) 对于NP中的每一个问题II1，。在NP完全问题II和NP困难问题II1间的差别是：II必须是NP类的而II1可能不 在NP中。2.2 NP完全性理论的证明2.2.1限制法限制的定义：通过对问题兀的实例加以限制得到一个已知NP完全问题的实例。例1三元集合的恰当覆盖(X3C)实例：有穷集S, |S|=3q, S的三元子集的集合C问：是否有C u C,使得S的每个元素恰好出现在C的一个成员中。证明：限制S = WuXuY|W
16、|=|X|=|Y|=qC = w,x,y|(w,x,y) eWxXxY 贝U|C |=q，且C中任两个元素都不交，成为3DM问题。例2最小覆盖问题实例：集合S的子集的集合C，正整数K。问：C是否有S的大小不超过K的覆盖，即是否包含子集C u C使得|C | =K且 uC = S？证明：限制VceC,|c|=3,|S|=3K,则为X3C问题。例3 集中集实例：集合S的子集的集合C，正整数K问：S是否包含C的大小不超过K的集中 集(hitting set)，即是否有子集S uS，使得|S |寸，且S至少包含C的每个子集的一个元素？证明：限制VceC,|c|=2,令V=S, E=C,则构成图G=(V
17、,E)的顶点覆盖问题。例4子图同构问题实例：图 G=(V1,E1), H=(V2，E2)问:G中是否有同构于H的子图，即是否有子集VcV, EcE，使得|V| = |V |,|E| = |E |, 1122且存在双射函数 f： V2V,使得u,veE2。(f(u),f(v)eE?证明：限制H为完全图，且|V2|=J,则该问题是团的问题.例5有界度的生成树实例：图G=(V,E),正整数K=|V|-1问：G是否包含一棵顶点度数不超过K的生成树，即是否有子集E cE,|E | = |V|-1,图G =(V,E)是连通的，且V中每个顶点至多包含在E的K条边中？证明：限制K=2,则为Hamilton通路
18、问题例 6 0-1 背包 Knapsack实例：有穷集U，VueU,大小s(u)eZ+,价值v(u)eZ+,大小的约束BeZ+,价值目标 KeZ+o问：是否有子集U cU，使得 s(u) K ueUueU证明：限制VueU,s( u) = v (u)ir i B = 2 sS K = 2 v(u)L 2 ueU2 ueU则成为均分问题。例7多处理机调度实例：有穷任务集A，VaeA,长度l(a) eZ+,处理机台数meZ+,截止时间DeZ+.问：是否存在不交的集合*,%,*，使得A = A1 u A2 u. u Ammax l(a):1 i mr(t) a(t)+l(t)d(t)Vt eT-t)
19、,b(t)+l(t ) d (t)若B为偶数，则存在均分B - BBr (t) = B, d (t) = B +1 = r (t) +1(t),必有。(t) = B.2222.2.3分量设计法分量设计法的定义 根据目标问题的实例设计分量(分量的成分与目标问题相关)， 实现已知NPC问题的实例(分量的功能与已知问题相关).3SAT变换到VC，其中分量 有真值安排分量、满足性检验分量等，这些分量都是子图，用来实现三元可满足性问题 的实例。例11最小拖延排序实例：任务集T，VteT，完成时间l(t)=1,截止时间d(t)eZ+.T上的偏序，非负整数K|T|问：是否存在可行调度b使得被拖延的任务数不超
20、过K，即b: Tt0,1,，|T|-1, 使得若 t以，则 b(t)b(t )若 tt，贝Ub(t)d(t)|=0； w =NextAdjVex (G， v， w)if (! visitedw) DFS (G， w)3.2.2流程图的设计与实现(1)建立邻接表流程图如下：图4建立邻接表流程图（2）深度优先遍历的流程图如下:图5深度遍历流程图3.3核心函数的描述3.3.1建立邻接表的函数函数名称：int CreateADG(ALGraph &g)函数功能：实现在键盘上输入有向图顶点数、顶点名称(用整数表示，如1就表示 顶点1)、弧数以及弧的顶点与起点，并用邻接表储存图。函数具体代码如下：int
21、CreateADG(ALGraph &g)(int i,j,k,l;ArcNode *p;int v1,v2;int c;printf(请输入有向图的顶点数:)；scanf(d，&g.vexnum);i=g.vexnum*(g.vexnum-1);printf(请输入有向图的边数:)；scanf(d，&g.arcnum);getchar();printf(请依次输入有向图的各个顶点：)；for(i=0;i=0)(printf(输入的顶点重复，请重新输入n)；i-;continue;g.verticesi.data=c;g.verticesi.firstarc二NULL;for(k=0;kg.a
22、rcnum;k+)(printf (-请输入第%d条弧的起点与终点(用逗号分隔)：,k+1);scanf(d,%d，&v1,&v2);i=locateALG(g,v1);j=locateALG(g,v2);if(i0|j0|i=j|(g.vexnumadjvex=j;p-nextarc二g.verticesi.firstarc;/顶点 i 的链表 g.verticesi.firstarc=p;/添加到最左边printf(n有向图的邻接表创建成功nn)；return 1;3.3.2深度优先遍历函数函数名称：void dfs(ALGraph G,int cur,int* save,int size
23、)函数功能：实现从选定的顶点开始对有向图进行深度优先遍历，函数中g为当前要 搜索的图，cur为当前搜索的顶点的下标，save是一个数组，用来保存搜索过的顶点， size为save数组的大小。在遍历中将遍历的顶点放入save中，当搜索到的顶点回到起 点时，为找到回路，打印出有向图的回路。函数的具体代码如下：void dfs(ALGraph G,int cur,int* save,int size)(int i;ArcNode *p=G.verticescur.firstarc;savesize=cur;while(p)(if(save0=p-adjvex)(count+;printf(第d 条回
24、路 ，count);for(i=0;i%d ，G.verticessavei.data,G.verticessavei+1.data);printf(d-%dn，G.verticessavei.data,G.verticessave0);else if(flagp-adjvex=0)(flagp-adjvex=1;dfs(G,p-adjvex,save,size+1);flagp-adjvex=0;p=p-nextarc;4测试数据及运行结果4.1程序测试及结果 E:瞒程序有向图课设DeKugL有向图诔没,exe”杀弧日勺 景瓠的 朱瓠的 亲瓠.的4个数:5各的的向图图有口，0有事 入入次占普
25、 顶边图青青青青青第第第第第鼠点与终点用逗号分 园点与终点用逗号分 园点与终点用逗号命 2上匕场占，田百日乙有向图的邻接表创建成功请输入开始顶点=1*.日.-口 nT-nT- 回回 案 1 2 第第一共2条回路是否继续？图7程序测试图1（2）当输入有向图为6个顶点，8条弧时，有向图如下:图8有向图26晅拽I请箱有向图的邻接表创建成功是否继续?一共3条回路请输入开始顶点543 - 2 2 2 nTKnTKnTK 回回回 is 12 3 第第第奏直霸嗣蓄葺？噌T 2 3 4 51务弧巍彪终点（用逗号分隔 2务弧的起点与终点用逗号分隔 3多弧的起点与终点用逗号分隔 或一遵弧的起点与终点用逗号登隔 认
26、第睡弧的起点与终点用逗号分隔 务弧的起点与终点用逗号分隔 多弧的起点与终点用逗号分隔 秦弧的起点与终点用逗号分隔图9程序测试图2（3）当输入有向图为5个顶点，4条弧时，此时有向图无回路，有向图如下:图10有向图3 E:睫程序有向图课设Deb有向图课设,exe -2 3 4 512 3 4 5 -T.J u T.J 4八只又各 3号号号号 2逗逗逗逗 i nnnnnnrrn 馨苫罟苫5 5冲终终终终 上善百己-己-5-6- 页-R-目荷后一祀五 T.-.!勺 勺.hn .mhw .mhm 有鬣m4 AAVAAAA A- rrr. - TTrIMKK - m.- rrr. - - rm J.#-l
27、.+-krr-krr4-.l.* 一请请请请请请请有向图的邻接表创建成功 请输入开始顶点:1共0条回路是否继续?图9程序测试图35调试心得在这次课程设计中，我做的题目是证明最长简单回路问题是NP完全问题。题目本 身不难，但涉及了很多算法设计与分析的知识，例如图的存储，图的遍历等。对于数据 结构学的不太好的我，还是有一定难度的。通过这次实验，我明白了算法设计与分析在整个学科领域里的重要性，使得我对数 据结构这门课有了更深的认识。锻炼了自己的动手能力，增强了程序设计编程能力。参考文献1 王晓东.算法设计与分析（第二版）.北京：清华大学出版社，2006.112 严蔚敏，吴伟明.数据结构（C语言版）M
28、.北京：清华大学出版社，20063 吕国英.算法设计与分析M.北京：清华大学出版社，20064 徐宝文，李志.C程序设计语音M.北京：机械工业出版社，2004附录源程序清单#include stdafx.h”#include #include#include typedef struct ArcNode (int adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针ArcNode;typedef struct VNode (int data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧VNode, Ad
29、jList50;typedef struct (AdjList vertices;int vexnum, arcnum; /图的当前顶点数和弧数ALGraph;int flag50; /这个是标志顶点是否被搜索过，flag1 = 1表示顶点1被搜索过， 否则没有被搜过过int count; /回路条数int locateALG(ALGraph g,int v) /v是顶点的值，locateALG 函数通过 v 值，返回顶点v在g的顶点数组的下标索引(for(int i=0;ig.vexnum;i+)(if(g.verticesi.data=v) /判断每个数组元素的值是否v，返回下标 retu
30、rn i;return -1; /没有找到使用链接表创建有向图int CreateADG(ALGraph &g)(int i,j,k,l;ArcNode *p;int v1,v2;int c;printf(请输入有向图的顶点数:)；scanf(d，&g.vexnum); /顶点数i=g.vexnum*(g.vexnum-1);printf(请输入有向图的边数:)；scanf(%d,&g.arcnum); /边数getchar();printf(请依次输入有向图的各个顶点：)；/首先输入各顶点的信息，依次输入第1个到第vexnum个顶点编号，使用整数for(i=0;i=0)(printf(输入的
31、顶点重复，请重新输入n)；i-;continue;g.verticesi.data=c;g.verticesi.firstarc二NULL;/这里输入边信息for(k=0;kg.arcnum;k+)(printf (-请输入第%d条弧的起点与终点(用逗号分隔)：,k+1);scanf(d,%d，&v1,&v2);i=locateALG(g,v1);j=locateALG(g,v2);这里判断输入的两个顶点是否都存在，否则重新输入if(i0|j0|i=j|(g.vexnumadjvex=j;p-nextarc二g.verticesi.firstarc;/顶点 i 的链表g.verticesi.f
32、irstarc=p;/添加到最左边printf(n有向图的邻接表创建成功nn)；return 1;使用深度优先搜索方法找出回路/g：当前要搜索的图/cur：当前搜索的顶点的下标/save数组：保存搜索过的顶点/size： save数组的大小void dfs(ALGraph G,int cur,int* save,int size)(int i;ArcNode *p=G.verticescur.firstarc; 取得顶点的链接表savesize=cur; /保存搜索过的顶点/遍历所有边while(p)(/save0是开始顶点搜索到的顶点回到起点，找到回路，打印if(save0=p-adjvex
33、)(count+;printf(第d 条回路 ，count);for(i=0;i%d，G.verticessavei.data,G.verticessavei+1.data);printf(d-%dn，G.verticessavei.data,G.verticessave0);顶点没有被搜索过，搜索这个顶点else if(flagp-adjvex=0)(flagp-adjvex=1; 标志已经搜索过dfs(G,p-adjvex,save,size+1);flagp-adjvex=0; 搜索回来，取消标志第27页共29页p=p-nextarc; 下一条边int main(void)(int save50;ALGraph g;int v;char sel;CreateADG(g); /创建有向图do(do(printf(n请输入开始顶点：)；/输入开始顶点
