基本算法选讲课件

1、基本算法和经典问题选讲中国科学技术大学袁平波主要内容穷举法贪心法回溯法一、穷举法（枚举法）列出问题的全部可能解，然后找到最佳解例： 设有A、B、C、D四个数都在116范围内。要求打印出四个数都不相同时，其和为34的所有值。算法分析：最直接的想法是设置A、B、C、D四个变量，都从1至16循环。需要164次。且循环中还必须判四数有所重复的情况。加上一定的限制条件设ABCD，A的初值为1，B的初值为A1，C的初值为B1，D的初值为C+1。每个循环的终值也可以算出：A + A+1 + A+2 + A+3 = 34 A=71 + B + B+1 + B+2 = 34 B=101 + 2 + C + C+

2、1 = 34 C15123D34D28算法实现函数void fournums() int a, b, c, d ;for (a = 1; a=7; a+) for (b = a+1; b=10; b+) for (c = b+1; c=15; c+) for (d = c+1; d=28; d+)if (a+b+c+d = 34) cout a ,b,c,d二、贪心法当一个问题的状态空间很大时，穷举法计算量可能会太大。当人们面对一个问题时，可能会采取目前看来最接近解状态的选择方案。有时运用最直接的方法，可能会得到很好的效果。贪心法一般原则贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那

3、些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。在某些情况下，贪心法得到的可能是最优解，但更多的情况下，可能只是近似解。有些问题，只有通过彻底地搜索才能得到最优解，从而使得求得最优解的代价甚高。这时候，也许求得一个与最优解相差不多的近似解（次优解）就可以满足要求。此时选用贪心法较好。例：多叉路口交通灯管理问题十字交叉路口要设置红绿灯来维持交通秩序，对于多叉路口需要设置几种颜色的交通灯才能使车辆之间既不相互碰撞，又能达到最大交通流量呢？假设有一个如下图所示的五叉路口，其中道路C和E是箭头所示的单行道。我们把可以同时行驶而不发生碰撞的路线用一种颜色的交通灯指示，对于以下的1

4、3种行驶路线，显然交通灯颜色越少则管理效率越高。多叉路口交通灯管理问题(2)13种行驶路线AB,AC,ADBA,BC,BDDA,DB,DCEA,EB,EC, ED不能同时行驶的路线AB、BC等多叉路口交通灯管理问题(3)借助于“图”。图中一个顶点表示一种行驶路线，行驶路线相互矛盾用顶点之间的连线线“边”来表示。原来的交通管理问题就变为：将图上顶点分组，使得有边相连的顶点不能在同一个组内。如果把图上的一个顶点理解为一个国家，顶点之间的连线表示两个国家有共同的边界，这个问题也就是著名的地图着色问题。不能通行的图示地图着色要求相邻的区域用不同的颜色，颜色尽量少地图着色（2）要求给出最少的着色分组的地

5、图。着色最优解问题。穷举法或回溯法来解决地图着色问题。对于小型地图可以使用对于大型地图，由于时间的指数上升，不可接受往往通过一些逼近方法来求近似最优解地图着色：贪心法用一种颜色给尽可能多的顶点着色选择某未着色的顶点并用该新颜色上色扫描未着色的其他各顶点，考察它们是否有边与该颜色着色的顶点相连，若没有边相连就用该颜色上色。换一种颜色重复前一步骤直到所有顶点全部着色为止贪心法近似解按1、2、3、4、5顺序着色最优解三、回溯法：八皇后问题要求在88格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击。由于皇后的走棋法是可以横走、直走、走斜线，每次走任意格数，所以要求这八个皇后中的任意两个都不处于同一行、

6、同一列或同一斜线上。问有多少种摆法？分析：穷举法。8个皇后各占一行，穷举每一行上可能占有的列，再排除不合条件的情况，只输出合理的解。八皇后问题的一个解解向量(1,3,5,7,2,0,6,4)八皇后问题的表示棋盘的行和列依次编上0, 1,给八个皇后依次编为7号，同时0至7号。由于要求每个皇后占有不同的行，可以令占有第i行的皇后编号为i。八后问题的全部解向量为(x0,x1,x7)。其中xi表示皇后i所处的列数。对于任何0i,j 7，ij有xixj，且没有两个皇后在同一斜线上，这样问题就缩小为在8!个可能解中寻找。问题的关键就在于怎样判断两个皇后不在同一条斜率为同一条斜率为1 的线上。斜率+1，i+

7、j=0, 1, , 14斜率-1，i-j=-7, 6, , 7表示一个皇后的控制范围A0.n-10.n-1来表示nn棋盘上的格，行号从上至下、列号左到右依次编号为0, 1,n-1。从右上角到左下角的主对角线及平行线(即斜率为+1的各斜线)上，元素的两个下标值的和(行号 + 列号)相等，从左到右的15条直线的这种和值分别为0, 1, 2, ,14。表示一个皇后的控制范围(续)同理，从左上角到右下角的主对角线及平行线(即斜率为-1的各斜线)上， (行号-列号)相等，从左到右的15条直线这种差值分别为-7, -6, -5, ，0, 1, 2，, 7。用以下的变量来表示当摆设第i个皇后时前面几个皇后在

8、各列、各对角线上的占用情况:bool An; / 第j列皇后bool B2*n-1; / 斜率为+1的对角线bool C2*n-1; / 斜率为-1， Ci-j+7C2*n-1回溯法图示“可行则进，不行则换、换不成则退”简化为4皇后问题。搜索过程如下:试探安排八个皇后从第0行开始，逐步安排每行皇后。对于每个皇后(设为第i个)，都是从第一列开始寻找位置，逐个查找直到找到正确的位置(设为第j列，则Aj、Bi+j、Ci-j+7都没有被占用)为止。如果找到了一个合适的位置，则标记Aj、Bi+j、Ci-j+7为被占用状态，并继续安排下一个皇后(第i+1个)；试探安排八个皇后（2）否则，如果找不到合适位置

9、，则说明前面的安排不太合理，应该退回(即“回溯”)到第i-1行的皇后，重新安排。如果8个皇后都安排好了，则打印这种方案;为了找到其它方案，也回溯，重新试探第7个（最后一个）皇后的下一种安排方法。从人工模拟的角度可直接从第6个回溯从算法的角度是继续试探第7个试探安排八个皇后（3）在回溯的过程中，应该抹掉前面试探留下的标记，即恢复Aj、Bi+j、Ci-j+7为未被占用状态，这样才能正确地开展下一步的试探。不管是找到了解还是没有找到解回溯时都必须抹掉以前的标记。这种回溯过程将逐步返回，使得各行的皇后都能试探到各种可能的摆法。回溯法的框架问题的解n元组(x0, x1,，xn-1)；void rectr

10、y(k) / 初始调rectry(0);置Xk为第一个可能值；while (Xk可能值没有试完) 设置Xk所涉及的标记if (X0, X1，Xn-1)是解)打印一组解;else rectry(k+1);回溯，抹去Xk涉及的标记；取下一个可能的Xk值;八皇后的递归算法void queen(int i) int j; for (j=0; j1)。这是一个递归过程。将1 个盘子从一个针上移到另一个针上。使用栈或递归经典问题（3）三、约瑟夫问题问题：有n 个人，围成一圈，从任何一个人开始，用1、2、3、n 按照顺时针为每个人编号。之后从第s 个人开始，按照顺时针方向从1 到m 报数，报到第m 个人出圈；接着从下一个人继续从1报数，继续出圈；直到所有的人都出圈为止。给出每个人的出圈次序。分析：使用一维数组变量a 记录各人的编号，令ai = i + 1。把出圈人的编