回溯法论文回溯法的分析与应用.docxVIP

沈阳理工大学算法实践与创新论文题目 回溯法的分析与应用学生姓名：学号：学生姓名：学号：学生姓名：学号：摘要对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内有哪些信誉好的足球投注网站，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,?,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。关键词: 回溯法 图的着色问题 符号三角形问题 图排列问题III第1章引言在现实世界中，有相当一类问题试求问题的全部解或求问题的最优解。最基本的方法是通过枚举法有哪些信誉好的足球投注网站问题的解空间。但许多问题解空间的大小随问题规模n的增长呈指数规律增长，这就使问题理论上可解而实际不可行。为了使有哪些信誉好的足球投注网站空间减少到尽可能小，就需要采用良好的有哪些信誉好的足球投注网站技术。回溯法就是一种较好的有哪些信誉好的足球投注网站技术。回溯法又称为试探法，它是一种有效的试探回溯有哪些信誉好的足球投注网站技术。即运用回溯法求解问题不是基于某种确定的法则，而是通过大量反复的试探和回溯。它的基本做法是有哪些信誉好的足球投注网站，能避免不必要搜素的穷举式有哪些信誉好的足球投注网站。回溯法在问题的解空间树中按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树，算法有哪些信誉好的足球投注网站至解空间树的任意一点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。简单地说，采用回溯法求解问题的整个过程贯穿了有哪些信誉好的足球投注网站---试探—决定回溯或前进这三种基本运算。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题”，“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中也产生很大的作用在学习过程中，我们会遇到这样的问题，让我们去寻找给定问题的解集或者让我们找出满足某些约束条件的最优解，这时候我们就可以采用回溯法来解决这一类的问题。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题”，“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中也产生很大的作用回溯法的优点是容易理解，可行性比较强。[1]第2章 回溯法的背景回溯法是一种穷举类型的算法，与其说它是一种算法，倒不如说它是一种试法。回溯法并没有什么高深的算法思想，虽然名字起的很高规格，但其实它的算法性连二分查找都比不上。这里说的算法性其实就是指技巧性，对问题特性了解越深入，越能创造出很巧妙的算法，在时间复杂度的级别上提高算法效率。这体现了算法效率与适用性之间的矛盾，二分查找效率很高，但适用性比较低，类似的还有著名的KMP算法。而穷举法效率最低，但几乎适用于所有问题。。回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少有哪些信誉好的足球投注网站空间，而这种减少不是一个一个解的减少，而是对有哪些信誉好的足球投注网站空间进行大规模剪枝，从而使得实际有哪些信誉好的足球投注网站空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。回溯法的应用背景说大很大，说小很小。算法大都在“不得不”的情况下才会使用，如果有别的算法，那它很有可能比回溯法高效，别忘了，回溯法是基于穷举的。回溯法适用于解排列组合类问题，也就是说目标解是从一个候选空间中选择出来的。从数量级上考虑，设候选空间的大小为n，如果选择是可重复的，那生成的有哪些信誉好的足球投注网站树为完全n叉树，有哪些信誉好的足球投注网站空间为n^n（如0-1背包问题，生成的解空间为高度为n完全二叉树，其中n为物体个数）。如果选择不能重复，那生成的解空间为n!(如TSP问题生成的解空间为n!,其中n为城市个数)。也就是说，当我们通过分析发现问题的解空间为n^n或者n!时，那很可能要用到我们的回溯法了。要用回溯法解决问题，那首先要确定问题的状态空间树。这个并不是很难，就看每一步选择有多少个可选值就可以了，第一步有8个可选值，那树第一层就有8个节点，第二步有5个可选值，那第一层每个节点都有5个分支，则第二层有8×5=40个节点，以此类推……到第n层一共有m1×m2×……×mn个节点，其中mi为第i步的可选值的个数。[2]确定了状态空间树，那下一步就是有哪些信誉好的足球投注网站了。这时候就体现出