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

《最长简单回路问题(论文)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关键词:最长简单回路问题摘要Keywords:ABSTRACT1绪论11」课题背景及廿的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•1I口I2.2.2冋溯法C语言举例63圆排歹IJ问题83.1

2、风

3、U丨扌出3.2算法设计83.2.1程序及思想93.2.2与圆排列随机算法的比较143.3算法效率164测试数据及运行结果185调

4、试心得19参考文献20附录211绪论1.1课程背景及目的算法设计与分析主要取材于算法设计与分析领域的经典内容，并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。1.2课题研究方法设计出高质量的算法，并

5、研究算法所耗费的计算资源与问题规模Z间的函数关系。算法设计与算法分析是不可分割的一个整体。算法分析的对象是被设计出的算法，而每一个被设计出的算法只有经过算法分析，才能评价其质量之优劣。计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂，计算量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题,这就产生了理论可计算而现实不可计算的孑盾。20世纪60年代以来，随着各个领域算法研究工作的发展，产生了一个崭新的研究领域，这就是算法的设计与分析。在这一方面已取巨大的进展，

6、它的研究成果对于计算机在各个领域的应用起着重要的作用。1.2.1基本内容按照算法所处理的对象进行分类，算法设计与分析主要冇数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、模式匹配等有关非数值计算的算法问题。按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为确定型算法、非确定型算法、交错型算法、随机型算法等（见计算复杂性理论）。另外，还有关于近似算法的研究。对于已经证明

7、不存在快速算法，或者至今还未找到快速算法的问题，例如NP完全问题（见NP完全性），与其花费人量的时间去寻找精确解，不如花费少量的吋间去寻找近似解。1.2.2基本概念设计算法与分析算法的复杂度，都与计算模型冇关，大多屈丁随机存取机器模型，这是一种确定型的串行计算模型。随机存取机器是一种理想的计算机，曲一个累加器、一个存储器和一个程序组成。存储器具有无限多个寄存器，每个寄存器可以存放任意大的一个自然数。程序是由一些最基本的指令所组成的序列，这些指令通常是指包括直接寻址与间接寻址在内的加、减、乘、除、取数、

8、存数、条件转移和停机。所冇的运算和逻辑判断都在累加器屮进行。问题的大小，也称问题的规模，通常用一个口然数作为随机存取机器输入数据量多少的度量。吋间复杂度和空间复杂度分别表示对于规模为n的输入问题、随机存取机器所耗费的时间与空间，它们都是n的函数。常用的时间和空间的度量方式是均匀耗费标准:执行一条指令算作耗费一个单位的空间，使用一个寄存器算作耗费一个单位的空间；另一种度量方式是对数耗费标准（见随机存取机器模型）。复朵度函数的计算方式又有两种：规模为n的所冇问题的复杂度的最人值称为最环情况复杂度；规模为n

9、的所有问题的复杂度的平均值称为平均情况复杂度。当规模n增加吋，复杂度的量级即极限属性称为渐近复杂度。由于理论计算机与现实计算机之间的差异，以及不同的现实计算机之是的差异，也由于算法设计与分析主要关心规模n比较大的情况，通常讨论的是渐近复朵度。1.2.3算法设计算法设计的任务是对各类具体的问题设计高质量的算法，以及研究设计算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和冋溯法等。（1）分治法把一个大规模问题划分成几个了问题，对每一个了问题采用同样的处理方法，求出各子问题的解答，再

10、把这些子问题的解答组合成整个问题的解答。（2）动态规划当整个问题的解答无法由少数儿个子问题的解答组合得岀，而依赖于大量子问题的解答，并冃子问题的解答又需耍反复利用多次时，系统地列表记录各个子问题的解答，据此求出整个问题的解答。（3）贪焚法在算法的每一步骤，都采取当前看来可行的或最优的策略。这是一种最直接的方法,只有在一些特殊情况下，贪婪法才能求出问题的解答。对于录求最优解的问题、贪婪法通常只能求出近似解。（4）回溯法和分叉截断法为了寻求问题的解答，有时需