算法课程论文

1、算法设计课程论文 题 目： 回 溯 法 班级: 10计算机科学与技术 姓 名: 郑云红 日 期: 2012年5月20日星期日 回 溯 法郑云红(温州大学物理与电子信息工程学院，10计算机科学与技术)摘要：在许多真实世界的问题中，像大多数NP难题一样，通过彻底的搜索有有限多个可能性的一个很大得数可以得到一个解决方案。而且，实际上所有的这些问题都不存在除穷尽搜索法之外的解决这些问题的算法。因此，产生了开发系统式的搜索技术的需要，希望把搜索空间减到尽可能的小。回溯法可以被描述为一个有组织的穷尽搜索，他常常可能避免搜索所有的可能性，它一般适合解决那些数据量比较大，但是有有限个解的问题。关键词：回溯法，

2、3着色问题，8皇后问题，一般回溯方法，剪枝。BacktrackingZheng Yun Hong(School of computer science and engineering, WenZhou University)( 10 Computer Science and Technology)Abstract: In many real world problems, as in most of the NP-hard problems, a solution can be obtained by exhaustively searching through a large but fin

3、ite number of possibilities. Moreover, for virtually all there problems, there does not exit an algorithm that uses a methods other than exhaustive search. Hence, the need arose for developing systematic techniques of searching, with the hope of cutting down the search space to possibility a much sm

4、aller space. Backtracking is described as an organized exhaustive search which often avoids searching all possibilities. It is generally suitable for solving problems where a potentially large but finite number of solutions have to be inspected.Keywords: backtracking, the 3-Coloring problem, the 8-Q

5、ueens problem, the general backtracking problem, Branch and Bound.前言：在许多问题中，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往是要使用回溯法，回溯法的基本做法是搜索，或是一种组织的井井有条的，能避免不必要搜索的穷举式搜索法，这种方法适用于解一些组合数相当大的问题。对于回溯法，其中最经典的几个问题就是着色问题和八皇后问题，这篇文章主要以讲解3着色问题和八皇后问题来帮助理解回溯法。回溯法主要是按照深度优先的策略，在搜索过程中通过一些基本的剪枝方法可以提高算法的效率。在这篇文章当中也会介绍一些基本的剪枝方

6、法。一、3着色问题：3着色问题描述：给出一个无向图G=(V,E)，需要用三种颜色之一为V中的每一个顶点着色，三种颜色分别是1,2,3，使得邻接的两个点的颜色不同，我们把这样的着色成为是合法的。否则，就是非法的，一种着色可以用n元组（c1 , c2 , cn）来表示，使ci1,2,3,1<=i<=n.例如，（1,2,2,3,1）表示一个有5个顶点的图的着色。一个n个顶点的图共有3n种可能的着色（合法的和非法的），所有可能的着色的集合可以用一颗完全的三叉树来表示，成为搜索树。在这棵树中，从根到叶节点的每一条路径代表一种着色指派。图1显示了有三个顶点的这样的一棵树。 图1，如果没有两个邻

7、接点的颜色相同，图的一个不完全着色部分称为部分解。回溯法通过每次一个节点地生成基底树来工作。如果从根到当前节点的路径对应于一个合法的着色，过程就终止（除非想找到不止一种的着色）。如果这条路径的长度小于n，并且相应的着色是部分的，那么就生成现结点的一个子节点，并将它标记为现结点。另一方面，如果对应的路径不是部分的，那么现结点标示为四节点并生成对应于另一种颜色的新节点。如果所有三种颜色都已经试过且没有成功，搜索就回到父节点，它的颜色被改变，以此类推。例如：考虑图a中所示的图，我们用颜色1,2,3对其顶点着色，图b所示的是在搜索一个合法的着色的过程中生成的搜索树的一部分。首先，在生成第三个节点之后，

8、发现着色（1,1）不是部分的，因此这个节点被标记为死节点，在图中用x表示。然后，b被指派为颜色2，并可以看到着色（1,2）是部分的，因此，生成对应于顶点c的一个新的子节点，赋予初始颜色值1，重复上述过程，忽略死节点和拓展那些相应的部分着色，我们最终到达合法的着色（1,2,2,1,3）。在图中注意两个重要的观察结论，它们概括出所有回溯算法的基本特征。首先，节点是用深度优先搜索的方法生成的；第二，不需要存储整棵搜索树，我们只需要存储根到当前活动节点的路径。事实上，根本没有生成有形的节点，整棵树是隐含的。在上面的例子中，我们只需要保存颜色指派的踪迹就可以了。算法：现在给出用回溯法求解3着色问题的两种

9、算法，一种是递归的，另一种是迭代的。在两种算法中，为了简单起见，都假定顶点集合为1，2，n，递归算法见算法3- COLORREC。算法3-COLORREC 输入：无向图G=(V，E)。 输出：G的顶点的3着色cln，其中每个cj为1，2或3。 1For k ß 1 to n 2 ck ß O 3end for 4Flag ß false 5. Graphcolor (1) 6If flag then output c7.else output “no solution”过程graphcolor(k) l for color= 1 to 3 2.ck ß

10、color 3 .if c为合法着色 then set flag ß true and exit 4.Else if c是部分的then graplwolor(k+1) 5end for 初始时没有顶点被着色，这由第l步中置所有颜色值为O指示。调用graphcolor(1)使得第一个顶点着色为l，很明显，(1)是部分着色，因此就以k=2递归调用过程，赋值语句使得第二个顶点也用l着色，得到的着色是(1，1)。如果顶点l和2没有边连接，那么这个着色就是部分的，否则，着色不是部分的，并且因此第二个顶点将用2来着色，得到的着色是(1,2)。第二个顶点着色之后，也就是说，如果当前的着色是部分的

11、，就用：3继续调用过程。依次类推。假定过程对于某个顶点，j>=3着色失败，这种情况在for循环执行三次而没有找到合法的或部分着色时将发生。在这种情况下，前一次递归调用被激活，并尝试将顶点j-1置为另一种颜色如果再一次出现三种颜色都没能导致一个部分着色的情况，那么最后递归调用的前一个被激活。这就是发生回溯的情况。前进与回溯的过程进行直到图或者着色，或者所有可能性都已经试过却找不到合法着色时才结束。检查着色是否是部分的可以递进地完成：如果着色向量c包含m个非0数，而且对于任何其他的颜色cm没有引起冲突，则它是部分的；否则它不是部分的。检查着色是否合法就是检查颜色向量是否由无矛盾的n种颜色组成

12、。 迭代回溯算法在算法3-COLOITER中给出。这个算法的主要部分由两个嵌套的while循环组成，内层的while循环实现前进(生成新节点)，而外层的while循环实现回溯的过程(即回到先前生成的节点)，这个算法的运作与前面递归形式的算法相似。算法2：输入：无向图 G=(V,E)。输出：G的顶点的3着色c1n，其中每个cj为1,2,3。1. for k ß 1 to n2. ck ß 03. end for4. flag ß false5. k ß 16. while k>=17. while ck <= 28. Ck ß ck

13、+ 19. If c 为合法着色 then set flag ß true 且从两个while循环退出10. else if c 是部分解then k ß k+1 前进11. End while12. Ck ß 013. K ß k-1回溯14. End while15. If flag then output c16. Else output “no solution”对于这两种算法的时间复杂性，我们注意到在最坏情况下生成了0(3n)个节点。对于每个生成的节点，如果当前着色是合法的、部分的，或者二者都不是，这需要O(n)的工作来检查。因此，在最坏情况下

14、，全部的运行时间是O( n3n)。 二、8皇后问题 经典的8皇后问题可以陈述如下：如何在8x8的国际象棋棋盘上安排8个皇后，使得没有两个皇后能互相攻击？如果两个皇后处在同一行、同一列或同一条对角线上，则她们能互相攻击。凡皇后问题类似地定义。在这样的情况下，有n个皇后和一个n*n的棋盘，n为任意值且n1。为了简化讨论，我们将研究4皇后问题，而且可以简单而直接地将其推广到n为任意值的情况。 考虑一个4*4的棋盘，由于没有两个皇后能处在同一行，所以每个皇后都在不同的行上。又因为每行有4个位置，就有44种可能的布局，每种可能的布局可以用一个有4个分量的向量x= xl，X2，X3，X4来描述。例如，向量

15、(2，3，4，1)对应于图a中所示的布局。如果在某行上没有皇后，则相应的分量为O（因此并不明确地包括在向量中）。例如，部分向量(3，1)对应于图b中的布局。 算法 为了用回溯法求解8皇后问题，算法尝试生成并以深度优先方式搜索一棵完全四叉有根树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置情况，依次类推。求解这个问题的回溯算法如算法4- QUEENS给出。在算法中，我们用术语“合法”来表示一个不互相攻击的4个皇后的放置，用术语“部分”来表示一个不互相攻击的少于4个皇后的放置。显而易见，放在位置xi和xj的两个皇后当且仅当x

16、i=xj时处在同一列上，不难看出两个皇后处在同一条对角线上当且仅当xi xj=i一j或xi xj=j-i。 算法13.3 4-QUEENS输入：空。输出：对应于4皇后问题的解的向量cl4。 1For k ß 1 to 4 2 ck ß 0 没有皇后放置在棋盘上 3end for 4Flag ß false 5. k ß 1 6While k>= 1 7while ck3 8 ck ß ck+l 9 If c为合法着色then set flag ß true且从两个while循环退出 10. else if c是部分解then k

17、 ß k+l 前进 11end while 12. ck ß 0 13. k ß k-l回溯 14end while 15If flag then output c16. else output “no solution”现在考虑一个求解一般的n皇后问题的蛮力方法。如前所述，由于没有两个皇后能放在同一列上则解向量必须是数1，2,n的一个排列。这样，蛮力方法可以改进为测n!种布局而不是nn种。然而，下面的论据说明回溯法极大地减少了测试的次数。考虑(n-2)!个向量，它们对应于前两个皇后放在第一列的那些布局，蛮力方法要盲目地测试所有这些向量而在回溯法中用O(1)次测试

18、就可以避免这些测试。尽管回溯法在最坏情况下要用O(nn)时间来求解n皇后问题，根据经验它在有效性上远远超过蛮力方法的O(n!)时间，作为它的可期望运行时间通常要快得多。三、一般的回溯法一般的回溯方法可以作为一种系统的搜索方法应用到一类搜索问题当中，这类问题的解由满足事先定义好的某个约束的向量（x1,x2,.,xi）组成。这里i是0到n之间的某个整数，其中n是一个取决于问题阐述的常量。在已经提到的两种算法3着色算法和8皇后问题当中，i是固定不变的。然而在一些问题中，i可以像下面的例子展开的那样，对于不同的解可能有所不同。考虑如下定义的PARTTION问题中的一个变形，给定一个n个整数集合X=x1

19、,x2xn和整数y，找出和等于y的X的子集Y。比如说，如果X=10,20,30,40,50,60，和y=60，则有三种不同长度的解，他们分别是10,20,30，20，40，60，设计出一个求解这个问题的回溯算法并不难，注意这个问题可以用另一种方法明确表达，使得解是一种明显长度为n的布尔向量，于是上面的三个解可以用布尔向量表示为1,1,1,0,0,0，0,1,0,1，0，0和0,0,0,0，0,1在回溯法中，解向量中每个xi都属于一个有限的线序集Xi,因此，回溯算法按词典序考察笛卡尔积X1* X2* * Xn中的元素。算法最初从空间向量开始，然后选择X 1中最小的元素作为x1，如果（x1）是一个

20、部分解，算法通过从X2中选择最小的元素作为x2继续，如果（x1，x2）是一个部分解，那么就包括X3中最小的元素，否则x2被置为X2中的下一个元素。一般的，假定算法已经检测到部分解为（x1，x2，xj），它然后再去考虑向量v=（x1，x2，xj，xj+1）,我们有下面的情况。(1) 如果v表示问题的最后解，算法记录下它作为一个解，在仅希望获得一个解时终止，或者继续去找出其他解。(2) (向前步骤)。如果v表示一个部分解，算法通过选择集合X j+2中的最小元素向前。(3) 如果v既不是最终解，也不是部分解，则有两种子情况 1、如果从集合Xj+1中还有其他的元素可选择，算法将x j+1 置为X j+

21、1中的下一个元素 2、（回溯步骤）。如果从集合Xj+1 中没有更多的元素可选择，算法通过将xj置为Xj中的下一个元素回溯；如果从集合Xj中任然没有其他的元素可选择，算法通过将xj-1置为Xj-1中的下一个元素回溯，以此类推。递归描述回溯算法：输入：集合X1，X2，Xn的清楚和隐含描述。输出：解向量v=（x1，x2，xi），0<=i<=n。1. V ß ()2. Flag ß false3. Advance(1)4. If flag then outout v5. Else output “no solution”过程Advance(k)1. For每个xXk2.

22、 xk ß x;将xk加入v3. If v 为最终解 then set flag ß true and exit4. Else if v 是部分解then Advance(k+1)5. End for迭代法描述回溯算法输入：集合X1，X2，Xn的清楚和隐含描述。输出：解向量v=（x1，x2，xi），0<=i<=n。1. V ß ()2. Flag ß false3. K ß 14. While k >= 15. While Xk没有被穷举6. xk ß Xk 中的下一个元素，将xk 加入v7. If v 为最终解th

23、en set flag ß true , 且从两个while循环退出8. Else if v是部分解 then k ß k+1 前进9. End while10. 重置 Xk 使得下一个元素排在第一位11. k ß k-1 回溯12. End while13. If flag then output v14. Else output “no solution”四、资料与课本进行比较 相同点：对于回溯法，都提及到了有关解空间树的概念；都用到了着色问题和8皇后问题这两个经典的回溯算法的例子；都通过迭代法和递归两种方法来描述回溯法。不同点：书本上所举的例子很多，更有助于

24、更深层次的理解回溯法，对于每一种实现方法，书本上对其复杂度及其算法效率都进行了分析，而该资料在这方面做的比较少。而且对于一些概念上的问题，书上讲得比资料上要详细，对于解空间树，书上讲得比较全面和清楚。而对于所举的例子，着色问题和8皇后问题。对于着色问题，对于资料上所述的仅仅只是m着色问题的一个特例3着色问题，而课本上则是比较有拓展性的展开了m着色问题。相对于课本上，单单介绍3着色问题更有助于对算法的理解，但是拓展性不强，在对算法的复杂度分析上，课本上说的相对较为详细，对于m着色问题，其算法的复杂度为：O(nmn)，在算法分析上，课本上给的代码较多，但是比较详细，资料上给的代码少，但是综合两种方

25、式来说，都方便理解回溯法，两种描述方法各有千秋。课本上综合m着色问题，详细分析了着色问题的过程，比较丰富。对于8皇后问题，资料上通过简单的介绍8皇后问题，然后引出n后问题，而且仅仅简单的介绍了一下n后问题，对于很多回溯法的问题都没有进行描述，比如说用什么解空间树解决问题，怎么样对在搜索过程中，对于不满足行，列和斜线约束的子树进行剪枝，但是课本上描述得很清楚；对于n后问题，通过迭代回溯方法比通过递归回溯方法效率要高，但是在资料中并没有阐述迭代回溯解决n后问题，但是在教材中对其进行了详细的描述。综合教材和资料，总体上来说资料上讲得比较浅，但是比较容易理解，教材上内容比较全面，案例多，拓展性强。五、自己对回溯法的理解与看法在我们所遇到的很多问题当中，我们既不能通过数学模型解决，也没有现成的算法可以用，或许必须通过遍历所有情况才能找出正确的结果，比如说迷宫问题，推箱子问题，红与黑问题，连连看问题等都要通过搜索才能找出结果，在搜索问题当中，主要分为深度优先和广度优先两种，在大多数深度优先搜索当中，都要用到递归与回溯的思想，运用回溯，主要是在搜索过程当中，当前点没有搜索过，走到当前点，发现当前点不合法，回到上一个点，另寻一条可行的路，当找不到可行解时继续向上回溯，依次类推，直到找到出口。对于回溯法，在搜索过程中比较常用，虽然对其进行了很多的优化，但是其效率还是比较低，搜索