算法分析与设计第5章

1、 每节一经典 掉头！退回到前一步第五章 回溯法第2讲 回溯法 对于回溯算法，更方便的是用递归控制方式实现，这种方式也可以解决任意的n皇后问题，算法的思想同样用深度优先搜索，在不满足约束条件时及时回溯。 这里，我们利用数组记录状态信息的技巧，用三个数组b, d, c分别记录棋盘上的n个列、2n-1个主对角线和2n-1个负对角线的占用情况。算法设计3：递归算法第2讲 回溯法 以四阶棋盘为例，如图，当n=4时，共有2n-1=7个主对角线，对应地也有7个负对角线。四皇后棋盘示意图n条n-1条第2讲 回溯法 用i，j分别表示皇后所在的行和列(即:i号皇后所在的列为j)，同一主对角线上的行列下标的差一样.

2、表达式i-j范围为-n+1n-1，为理解简便，我们对-n+1n-1两边同时增加n, 则i-j变为i-j+n，其取值范围为12n-1，用i-j+n对主对角线进行编号。同样地，负对角线上行列下标的和一样，用表达式i+j编号，则范围为22n。12345672634578第2讲 回溯法 int a20,b20,c40,d40; int n,t,i,j,k; /t记录解的个数，i控制行，j控制列 main( ) int i, input(n); /输入皇后的个数 for(i=1;i=n;i+) bi=0;/记录棋盘n个列 ci+1=0; cn+i=0;/记录棋盘负对角线 di=0; dn+i-1=0;/

3、记录棋盘主对角线 try（1）; 递归回溯算法初始化12345672634578b1b2b3b4第2讲 回溯法try(int i) int j; for(j=1;j=n;j+) /j表示列号，第i个皇后有n种可能位置 if (bj=0) and (ci+j=0) and (di-j+n=0)/判断位置是否冲突 ai=j; /第i行第j列可以摆放编号为i的皇后 bj=1; /占领第j列 ci+j=1; di-j+n=1; /占领两个对角线 if (in) try(i+1); /n个皇后没有摆完， 递归摆放下一皇后 else output( ); /完成任务，打印结果 bj=0; ci+j=0;

4、di-j+n=0; /回溯，清理现场，从低向上回溯 12345672634578b1b2b3b4第2讲 回溯法output( ) t=t+1;/这里的t只是用来统计满足条件的解 的个数 print(t, ); for( k=1;k0(有路可走)and (未达到目标) /还未回溯到头 if (in) /搜索到叶节点 搜索到一个解，输出; else /正在处理第i个元素 ai第一个可能的值； while (ai不满足约束条件 且 在搜索空间内) ai下一个可能的值； if (ai在搜索空间内) 标识占用的资源; i=i+1; / 扩展下一个结点 else 清理所占的状态空间；i=i-1; /回溯非

5、递归回溯框架第2讲 回溯法int an;try(int i)if （in） 输出结果; else for（ j=下界 ; jn or xm or x1 or y1) print(x,y error!); return; for(i=1;i=;i+) for(j=1;j=;j+) aij=0; axy=1; find(x,y,2); /2为深度dep if (count=0 ) print(“No answer!”); else print(“count=!”,count); 4、算 法初始化第2讲 回溯法find(int y,int x,int dep) int i , xx , yy ;fo

6、r i=1 to 8 do /加上方向增量,形成新的坐标 xx=x+fxi; yy=y+fyi; if (check(xx,yy)=1) /判断新坐标是否出界,是否已走过? axx,yy=dep; /走向新的坐标 if (dep=n*m) output( ); else find(xx,yy,dep+1); /从新坐标出发,递归下一层 axx,yy=0; /回溯,恢复未走标志 第2讲 回溯法 output( ) count=count+1;/count用来记录满足约束的解个数 print(“换行符”); print(count=,count); for x=1 to n do print(“换

7、行符”); for y=1 to m do print(ax,y); 第2讲 回溯法例3: 输出自然数1到n所有不重复的排列，即n的全 排列 如：n=3则n的全排列为： 123 132 213 231 312 321 排列及排列树的回溯搜索第2讲 回溯法 n的全排列是一组n元一维向量:(x1,x2,x3,xn),搜索空间是:1xin,i=1,2, 3,n,约束条件很简单,xi互不相同。 这里我们采用第三章“3.2.3利用数组记录状态信息”的技巧,设置n个元素的数组d,其中的n个元素用来记录数据1-n的使用情况,已使用置1,未使用置0.1、算法设计第2讲 回溯法1、算法描述算法描述初始化空排列，

8、开始逐位进行排列；循环，直到第一位出现回溯 寻找当前位的下一个可排列数字； 若存在可排列数字 排列 若已排列满，则 输出一个排列，并删除该位（准备下一个排列） 否则 准备排列下一位 退回上一位，并删除所排列数字第2讲 回溯法main（ ） int j,n, print(Input n= ); input(n); for(j=1;j=r;j+) dj=0; try(1); 2、算法初始化第2讲 回溯法try(int k) int j; for(j=1;j=n;j+) if (dj=0) ak=j; dj=1; else continue; if (kn) try(k+1); /准备排列下一位 e

9、lse p=p+1; output( );/列已排满，则输出一个排列 dak=0; /回溯第2讲 回溯法 output( ) int j; print(p,”:”) for(j=1;j=n;j+) print(aj); print(“换行符”); 3、算法说明：变量p记录排列的组数，k为当前处理的 第k个元素第2讲 回溯法 以上用回溯法完成的全排列问题的复杂度为O(nn),并不是一个好的算法。因此不可能用它的结果去搜索排列树。4、算法分析第2讲 回溯法全排列算法另一解法搜索排列树的算法框架1、算法设计 根据全排列的概念，定义数组初始值为（1，2，3，4，n），这是全排列中的一种，然后通过数据间

10、的交换，则可产生所有的不同排列。第2讲 回溯法int a100,n,s=0; main( ) int i,; input(n); for(i=1;in) output( ); else for(j=t;j=n;j+) swap(t,j);/进行调换下标为t,j try(t+1); swap(t,j); /回溯时，恢复原来的排列 第2讲 回溯法output( ) int j; printf(n); for( j=1;j=n;j+) printf( mod d,aj); s=s+1;swap(int t1,int t2) int t; t=at1; at1= at2; at2=t;输出结果交换数据

11、第2讲 回溯法 1)有的读者可能会想try( )函数中,不应该出现自身之间的交换,for循环是否应该改为 for(j=t+1;jn显然是位数多的话,数据一定大;i=n时,由于尝试是由小到大进行的,位数相 等时后来满足条件的数据一定比前面的大。第2讲 回溯法main( ) int A101,B101; int i,j,k,n,r； A1=1; for(i=2;i=100;i+) /置初值：首位为1 其余为0 Ai=0; n=1; i=1; while(A1=n) /发现有更大的满足条件的高精度数据 n=i; /转存到数组B中 for (k=1;k=n;k+) Bk=Ak; 3、算法 初始化第2讲

12、 回溯法 i=i+1;r=0; for(j=1;j=i;j+) /检查第i位是否满足条件 r=r*10+Aj; r=r mod i; if(r0) /若不满足条件 Ai=Ai+i-r ; /第i位可能的解 while (Ai9 and i1) /搜索完第i位的解，回 溯到前一位 Ai=0; i=i-1; Ai=Ai+i; 第2讲 回溯法 1）从A1=1开始，每增加一位Ai(初值为0)先计算r=(A1*10i-1+A2*10i-2+Ai)，再测试r=r mod i是否为0。 2）r=0表示增加第i位后,满足条件,与原有满足条件的数(存在数组B中)比较,若前者大,则更新后者(数组B),继续增加下一

13、位。 3）r0表示增加i位后不满足整除条件,接下来算法中并不是继续尝试Ai= Ai+1,而是继续尝试Ai= Ai +i-r,因为若Ai=Ai+i-r9时,要进位也不能算满足条件.这时,只能将此位恢复初值0且回退到前一位(i=i-1)尝试Ai= Ai +i。这正是最后一个while循环所做的工作。 5）当回溯到i=1时,A1加1开始尝试首位为2的情况,最后直到将A1=9的情况尝试完毕,算法结束。第2讲 回溯法 n个作业要在由2台机器M1和M2组成的流水线上完成加工.每个作业加工的顺序都是先在M1上加工,然后在M2上加工.M1和M2加工作业i所需的时间分别为ai和bi.流水作业调度问题要求确定这n

14、个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少.作业在机器M1、M2的加工顺序相同。例5: 流水作业车间调度第2讲 回溯法t机器1机器2A21B31C23机器1机器2012345678910111201234567891011120123456789101112理解模型ABC : 10 S第2讲 回溯法t机器1机器2A21B31C23机器1机器2012345678910111201234567891011120123456789101112理解模型CBA : 8 S第2讲 回溯法t机器1机器2A21B31C23机器1机器201234

15、5678910111201234567891011120123456789101112理解模型CAB : 8 S第2讲 回溯法t机器1机器2A21B31C23机器1机器2012345678910111201234567891011120123456789101112理解模型BCA : 9 S第2讲 回溯法 1) 问题的解空间是一棵排列树，简单的解决方法就是在搜索排列树的同时,不断更新最优解，最后找到问题的解。算法框架和例6完全相同,用数组x(初值为1，2，3，n)模拟不同的排列，在不同排列下计算各种排列下的加工耗时情况。1、算法设计这3个作业的6种可能的调度方案是：A,B,C;A,C,B;B,

16、A,C;B,C,A;C,A,B;C,B,A;它们所相应的完成时间和分别是10，8，9，9，8，8。易见，最佳调度方案是A,C,B; C,A,B;C,B,A其完成时间和为8。第2讲 回溯法1、算法设计BACFGLMDHINOEJKPQ1243344324422332解空间排列树第2讲 回溯法 2）机器M1进行顺序加工,其加工f1时间是固定的, f1i= f1i-1+axi.机器M2则有空闲如(图1)或积压如(图2)的情况,总加工时间f2,当机器M2空闲时,f2i=f1i+ bxi;当机器M2有积压情况出现时,f2i= f2i-1+ bxi.总加工时间就是f2n。a1a2b1b2a1a2b1b2图

17、(1)有空闲图(2)有积压第2讲 回溯法 3）一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，当作业按在机器M1上由小到大排列后，机器M2的空闲时间较少，当然最少情况一定还与M2上的加工时间有关，所以还需要对解空间进行搜索.排序后可以尽快地找到接近最优的解,再加入下一步限界操作就能加速搜索速度。第2讲 回溯法 4)经过以上排序后,在自然数列的排列下,就是一个接近最优的解.因此,在以后的搜索过程中, 当某一排列的前面几步的加工时间已经大于当前的最小值,就无需进行进一步的搜索计算,从而可以提高算法效率。第2讲 回溯法 1)用二维数组job1002存储作业在M1、M2上

18、的加工时间。 2)由于f1在计算中,只需要当前值,所以用变量存储即可;而f2在计算中,还依赖前一个作业的数据,所以有必要用数组存储。 3)考虑到回溯过程的需要,用变量f存储当前加工所需要的全部时间。2、数据结构设计第2讲 回溯法int job1002,x100,n，f1=0,f=0,f2100=0;main( ) int j; input(n); for(i=1;i=2;i+) for(j=1;j=n;j+) input(jobji); try(1);3、算 法初始化第2讲 回溯法 try(int i) int j; if (i=n+1) for(j=1;j=n;j+)/输出排列方式 bestxj=xj; bestf=f;/该排列方式所对应的时间 else第2讲 回溯法 for(j=1;jf1) f2i= f2i-1+jobxj2;/M2有积压的情况 else f2i= f1+jo