算法第5章-第2讲-回溯算法2递归形式课件.ppt

《算法第5章-第2讲-回溯算法2递归形式课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、每节一经典掉头！退回到前一步第五章回溯法第2讲回溯法对于回溯算法，更方便的是用递归控制方式实现，这种方式也可以解决任意的n皇后问题，算法的思想同样用深度优先搜索，在不满足约束条件时及时回溯。这里，我们“利用数组记录状态信息”的技巧，用三个数组c,b,d分别记录棋盘上的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+1～n-1，为理解简便，我们对-n+1～n-1两边同时增加n,则i-j变为i-j+n，其取值范围为1～2n-1，用i-j+n对主对角线进行编号。同样地，负对角线上行列下标的和一样，用表达式i+j编号，则范围为2～2n。12345672634578第2讲回溯法inta[20],b[20],c[40],d[40];intn,t,i,j,k;//t记录解的个数，i控制行，j控制列main(){inti,input(n);//输入皇后的个数for(i=1;i<=n;i++){b[i]=0;//记录棋盘n个列c[i+1]=0;c[n

3、+i]=0;//记录棋盘负对角线d[i]=0;d[n+i-1]=0;//记录棋盘主对角线}try（1）;}递归回溯算法初始化12345672634578b[1]b[2]b[3]b[4]第2讲回溯法try(inti){intj;for(j=1;j<=n;j++)//j表示列号，第i个皇后有n种可能位置if(b[j]=0)and(c[i+j]=0)and(d[i-j+n]=0)//判断位置是否冲突{a[i]=j;//第i行第j列可以摆放编号为i的皇后b[j]=1;//占领第j列c[i+j]=1;d[i-j+n]=1;//占领两个对角线if(i

4、;//n个皇后没有摆完，递归摆放下一皇后elseoutput();//完成任务，打印结果b[j]=0;c[i+j]=0;d[i-j+n]=0;//回溯，清理现场，从低向上回溯}}12345672634578b[1]b[2]b[3]b[4]第2讲回溯法output(){t=t+1;//这里的t只是用来统计满足条件的解的个数print(t,'');for(k=1;k<=n;k++)print(a[k],'');print(“换行符”);}算法3递归回溯：第2讲回溯法递归算法的回溯是由函数调用结束自动完成的，也不需要指出回溯点，（类似算法2中的k=k-1）,但需

5、要“清理现场”——将当前点占用的位置释放，也就是算法try()中的后三个赋值语句。递归回溯算法说明第2讲回溯法回溯算法思想与框架回溯法基本思想算法设计过程算法框架第2讲回溯法回溯法是在包含问题的所有解的解空间树(或森林)中.按照深度优先的策略,从根结点出发搜索解空间树.算法搜索至解空间树的任一结点时,总是先判断该结点是否满足问题的约束条件。如果满足则进入该子树,继续按深度优先的策略进行搜索.否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。回溯法就是对隐式图的深度优先搜索算法.(隐式图指问题的解空间多是树形或图形结构，并没有显式给出)回溯法基本思想第

6、2讲回溯法四皇后问题的解空间树4!=24leaves2157346101289111517131416212319202226282425273133293032373935363842444041434749454648535551525458605657596365616264183450x1=1x1=2x1=3x1=422133311444xi表示第i个皇后所在位置的列号x2=2x3=3x4=4x3=4x4=3第2讲回溯法确定问题的解空间在应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个解。确定结点的扩展规则如：每个皇后在

7、一行中的不同位置移动，而象棋中的马只能走“日”字等。搜索解空间回溯算法从开始节点(根节点)出发，以深度优先的方式搜索整个解空间。算法设计过程第2讲回溯法算法设计过程搜索解空间搜索开始的结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，以深度优先方式移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为

8、止。第2讲回溯法21573461012