最长简单回路问题(论文)

最长简单回路问题最长简单回路问题摘要关键词：；；；最长简单回路问题ABSTRACTKeywords:;;;最长简单回路问题目录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附录…………………………………………………………………………….……………..21最长简单回路问题第1页共29页1绪论1.1课程背景及目的算法设计与分析主要取材于算法设计与分析领域的经典内容，并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。1.2课题研究方法设计出高质量的算法，并研究算法所耗费的计算资源与问题规模之间的函数关系。算法设计与算法分析是不可分割的一个整体。算法分析的对象是被设计出的算法，而每一个被设计出的算法只有经过算法分析，才能评价其质量之优劣。计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂，计算量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题，这就产生了理论可计算而现实不可计算的矛盾。20世纪60年代以来，随着各个领域算法研究工作的发展，产生了一个崭新的研究领域，这就是算法的设计与分析。在这一方面已取巨大的进展，它的研究成果对于计算机在各个领域的应用起着重要的作用。1.2.1基本内容按照算法所处理的对象进行分类，算法设计与分析主要有数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、模式匹配等有关非数值计算的算法问题。按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为确定型算法、非确定型算法、交错型算法、随机型算法等（见计算复杂性理论）。另外，还有关于近似算法的研究。对于已经证明不存在快速算法，或者至今还未找最长简单回路问题第2页共29页到快速算法的问题，例如NP完全问题（见NP完全性）,与其花费大量的时间去寻找精确解，不如花费少量的时间去寻找近似解。1.2.2基本概念设计算法与分析算法的复杂度，都与计算模型有关，大多属于随机存取机器模型，这是一种确定型的串行计算模型。随机存取机器是一种理想的计算机，由一个累加器、一个存储器和一个程序组成。存储器具有无限多个寄存器，每个寄存器可以存放任意大的一个自然数。程序是由一些最基本的指令所组成的序列，这些指令通常是指包括直接寻址与间接寻址在内的加、减、乘、除、取数、存数、条件转移和停机。所有的运算和逻辑判断都在累加器中进行。问题的大小，也称问题的规模，通常用一个自然数作为随机存取机器输入数据量多少的度量。时间复杂度和空间复杂度分别表示对于规模为n的输入问题、随机存取机器所耗费的时间与空间，它们都是n的函数。常用的时间和空间的度量方式是均匀耗费标准：执行一条指令算作耗费一个单位的空间，使用一个寄存器算作耗费一个单位的空间；另一种度量方式是对数耗费标准（见随机存取机器模型）。复杂度函数的计算方式又有两种：规模为n的所有问题的复杂度的最大值称为最环情况复杂度；规模为n的所有问题的复杂度的平均值称为平均情况复杂度。当规模n增加时,复杂度的量级即极限属性称为渐近复杂度。由于理论计算机与现实计算机之间的差异，以及不同的现实计算机之是的差异，也由于算法设计与分析主要关心规模n比较大的情况，通常讨论的是渐近复杂度。1.2.3算法设计算法设计的任务是对各类具体的问题设计高质量的算法，以及研究设计算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。（1）分治法把一个大规模问题划分成几个子问题，对每一个子问题采用同样的处理方法，求出各子问题的解答，再把这些子问题的解答组合成整个问题的解答。（2）动态规划当整个问题的解答无法由少数几个子问题的解答组合得出，而依赖于大量子问题的解答，并且子问题的解答又需要反复利用多次时，系统地列表记录各个子问题的解答，据此求出整个问题的解答。最长简单回路问题第3页共29页（3）贪婪法在算法的每一步骤，都采取当前看来可行的或最优的策略。这是一种最直接的方法，只有在一些特殊情况下，贪婪法才能求出问题的解答。对于录求最优解的问题、贪婪法通常只能求出近似解。（4）回溯法和分叉截断法为了寻求问题的解答，有时需要在所有的可能性(称为候选对象)中进行系统的搜索，例如在寻求最优解的问题中，就常碰到这种情况。这时，须把各种候选对象组织成一棵树，每个树叶对应着一个候选对象,于是每个内部顶点就表示若干个候选对象(即在此顶点下面的树叶)。回溯法是从树根开始按深度优先搜索的原则向下搜索,即沿着一个方向尽量向下搜索,直到发现此方向上不可能存在解答时，就退到上一个顶点，沿另一个方向进行同样的工作。分叉截断法也是从树根开始向下搜索，不同的是，分叉截断法常常利用一个适当选取的评估函数，来决定应该从哪一点开始下一步搜索（分叉），以及哪一点下方不可能存在解答，从而这点的下方不必进行搜索（截断）。评估函数选得好，就会很快地找到解答，选得不好，就可能找不到解答或者找到的不是最优解（有时它可以作为最优解的一个近似解）。（5）算法分析对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法,采用不同的分析方法。讨论某些问题类在一定的计算模型中的任意算法的复杂度至少是多大，也是算法分析的一个内容，这就是下界问题。通常认为，多项式复杂度的算法是现实可行的，而指数复杂度的算法是现实不可行的。最长简单回路问题第4页共29页2NP完全性理论的介绍2.1NP完全性理论2.1.1基本概念一般来说，把可由多项式时间算法求解的问题看作易处理问题，而将未能找到多项式时间算法求解的问题视作难处理问题。而这种所谓的难处理问题我们称之为NP难度或NP完全问题。这类问题有一个共同特征：一个NP完全问题可以在多项式时间求解，当且仅当所有其他NP完全问题都可以在多项式时间求解。如果任意一个NP难度问题存在一个多项式时间算法，那么，所有NP完全问题都可以有多项式时间算法。在研究NP完全理论时，通常很容易重述一个问题使其解只有两个结论：yes或no。这种情况下，称问题为判定问题。与此相对照，最优化问题是关心某个量的最大化或最小化的问题。下面描述了怎样转化为这两类问题。例如：设S是一个实数序列，ELEMENTUNIQUENESS问题为，是否S中的所有的数都是不同的。判定问题：ELEMENTUNIQUENESS输入：一个整数序列S输出：在S中存在两个相等的元素吗最优问题：ELEMENTCOUNT输入：一个整数序列S输出：一个在S中频度最高的元素2.1.2基本分类（1）P类定义1设A是求解问题II的一个算法，如果在展示问题II的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。因此如果对于同样的输入，实例一遍又一遍的执行，它的输入从不改变。定义2判定问题的P类由这样的判定问题组成，它们的yes/no解可以用确定性算法在运行多项式步数内。最长简单回路问题第5页共29页例如：排序问题：给出一个n个整数的表，它们是否按非降序排列？不相交集问题：给出两个整数集合，它们的交集是否为空？（2）NP类NP由这样的问题II组成，对于这些问题存在一个确定性算法A，该算法在对II的一个实例展示一个断言解时，它能在多项式时间内验证解的正确性。即如果断言解导致答案是yes，就存在一中方法可以在多项式时间内验证这个解。为了较形式的定义这个类，必须首先定义不确定性算法的概念.对于输入x,一个不确定性算法由下列两个阶段组成：(a)猜测阶段：在这个阶段产生一个任意字符串y，它可能对应于输入实例的一个解，也可以不对应解。（O(ni)）(b)验证阶段：在这个阶段，一个确定性算法验证两件事。首先，它检查产生的解串y是否有合适的形式，如果不是，则算法停下来并回答no；另一方面，如果y是合适形式，那么算法继续检查它是否是问题实例x的解，如果确实是，那么它停下来且回答yes，否则回答no。我们也要求这个阶段在多项式步数内完成。（O(nj)）对于一个（不确定性）算法的运行时间，它仅仅是两个运行时间的和：一个是猜测阶段的时间，另一个是验证阶段的时间。因此它是O(ni)+O(nj)=O(nk)，k是某个非负整数。定义3判定问题类NP由这样的判定问题组成：对于它们存在着多项式时间内运行的不确定性算法。类P和NP之间，有下面的不同点：（a）P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出；（b）NP是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内检查或验证它们的解。（3）NP完全问题术语NP完全表示NP中判定问题的一个子类，它们在下述意义上是最难的，即如果它们中的一个被证明用多项式时间确定算法可解，那么NP中的所有问题用多项式时间确定性算法可解，即NP=P。定义4设II和II1是两个判定问题。如果存在一个确定性算法A，它的行为如下：当给A展示问题II的一个实例I时，算法A可以把它变换为问题II1的实例I1，使得当最长简单回路问题第6页共29页且仅当I1回答yes时，对I回答yes。而且，这个变换必须在多项式时间内完成。那么我们说II多项式时间归约到II1，用符号1polyIIII表示。定义5一个判定问题II称为是NP困难的，如果对于NP中的每一个问题II1，。定义6一个判定问题II称为是