八皇后问题详细的解法PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,八皇后问题,2,1,八皇后问题背景,2,盲目的枚举算法,3,加约束的枚举算法,4,回溯法及基本思想,5,回溯法应用,6,八皇后问题的递归回溯算法,7,八皇后问题的非递归回溯算法,3,【,背景,】,八皇后问题是一个以国际象棋为背景的问题：,如何能够在,88,的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。,4,八皇后问题,要在,8*8,的国际象棋棋盘中放,8,个皇后，使任意两个皇后都不能互相吃掉。,规则：皇后能吃掉同一行同一列、同一对角线的任意棋子。求所有的解。,八皇后的两组解,5,【,问题分析,】,设八个皇后为,x,i,，分别在第,i,行,(i=1,，,2,，,3,，,4,，,8),；,问题的解状态,：可以用,(1,x,1,),，,(2,x,2,),，,，,(8,x,8,),表示,8,个皇后的位置；,由于行号固定，可简单记为：,(x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,),；,问题的解空间,：,(x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,),，,1x,i,8(i=1,，,2,，,3,，,4,，,8),，共,8,8,个状态；,约束条件,：八个,(1,x,1,),2,x,2,),(3,x,3,),(4,x,4,),(5,x,5,),(6,x,6,),(7,x,7,),(8,x,8,),不在同一行、同一列和同一对角线上。,原问题即：在解空间中,寻找符合约束条件,的解状态。,按什么顺序去搜？,目标是没有漏网之鱼，尽量速度快。,6,枚举得有个顺序，否则轻则有漏的、重复的；重则无法循环表示。,2【,问题设计,】,盲目的枚举算法,a,盲目的枚举算法,通过,8,重循环模拟搜索空间中的,8,8,个状态；,按,枚举思想,，,以,DFS,的方式,，从第,1,个皇后在第,1,列开始搜索，枚举出所有的“解状态”：,从中找出满足约束条件的“答案状态”。,约束条件？,1.,按什么顺序去查找所有的解,a.,盲目的枚举算法,void main()int x100;for(x1=1;x1=10;x1+)for(x2=1;x2=10;x2+)for(x3=1;x3=10;x3+)for(x4=1;x4=10;x4+)for(x5=1;x5=10;x5+)for(x6=1;x6=10;x6+)for(x7=1;x7=10;x7+)for(x8=1;x8=10;x8+),if(,check(x)=0,),printf(x);,7,该如何解决冲突的问题呢？,1.,行；我们是按照行枚举的，保证了一行一个皇后；,2.,列：判断是否存在,xi=xj,3.,对角线：主对角线的,i-j,与从对角线的,i+j,存在特殊关系，如图：,8,9,盲目的枚举算法,约束条件？,不在同一列：,x,i,x,j,；,不在同一主对角线上：,x,i,-i,x,j,-j,；,不在同一负对角线上：,x,i,+i,x,j,+j,。,违规的情况可以整合改写为：,abs(,x,i,-,x,j,)=abs(i-j)or(,x,i,=,x,j,),10,盲目的枚举算法,queen1(),int,a9;,for,(a1=1;a1=8;a1+),for,(a2=1;a2=8;a2+),for,(a3=1;a3=8;a3+),for,(a4=1;a4=8;a4+),for,(a5=1;a5=8;a5+),for,(a6=1;a6=8;a6+),for,(a7=1;a7=8;a7+),for,(a8=1;a8=8;a8+),if,(check(a,8)=0),continue,;,else,for,(i=1;i=8;i+),print(ai);,check1(a,n),int,i,j;,for,(i=2;i=n;i+),for,(j=1;j=i-1;j+),if,(ai=aj,),or,(,abs,(,ai-aj)=,abs,(i-j),return,(0);,return,(1);,双重循环，任意两个皇后之间都必须检查。,用,a1a8,存储,x,1,x,8,11,有,“,通用的解题法,”,之称。,回溯法的基本做法是,搜索,，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。,回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,1,回溯法,回溯法指导思想,走不通，就掉头。,12,求问题所有解：要回溯到根，且根结点的所有子树都已被搜索遍才结束。,求任一解：只要搜索到问题的一个解就可结束。,1,回溯法,13,1,回溯算法设计过程,step1,确定问题的解空间；,step2,确定结点的扩展规则；,step3,搜索解空间。,14,2,回溯法应用,-,加约束的枚举算法,如果能够排除那些没有前途的状态，会节约时间；,如何提前发现？,回溯法指导思想,走不通，就掉头,如,(1,1,x,3,x,4,x,5,x,6,x,7,x,8,),没有必要再扩展；,这种状态扩展后会产生,8,6,个结点；,同样的,(1,2,x,3,x,4,x,5,x,6,x,7,x,8,),，,也应被排除。,在每一次扩展,E,结点后，都进行检查；,对检查结果如何处理？,检查合格的才继续向下扩展；,遇到不合格的“掉头就走”。,只要当前枚举到的状态可行，就继续枚举下去。当找到一种方案或者无法继续枚举下去时，就退回到上一状态。退回到上一状态的过程叫做回溯，枚举下一个状态的过程叫做递归。,回溯就是像人走迷宫一样，先选择一个前进方向尝试，一步步试探，在遇到死胡同不能再往前的时候就会退到上一个分支点，另选一个方向尝试，而在前进和回撤的路上都设置一些标记，以便能够正确返回，直到达到目标或者所有的可行方案都已经尝试完为止。,15,16,2,回溯法应用,-,例,1 b,加约束的枚举算法,我们可以依次确定每一行皇后的位置,如果在某一列可以放下一个皇后，我们就在这里放下，并搜索下一行,若无法放下皇后则回到上一行，即回溯,当,n,行的皇后都已确定后，我们就找到了一种方案,17,18,2,例,1 b,加约束的枚举算法,queen1(),int,a9;,for,(a1=1;a1=8;a1+),for,(a2=1;a2=8;a2+),if,(check(a,2)=0),continue,;,for,(a3=1;a3=8;a3+),if,(check(a,7)=0),continue,;,for,(a8=1;a8=8;a8+),if,(check(a,8)=,0),continue,;,else,for,(i=1;i=8;i+),print(ai);,此算法可读性很好，体现了“回溯”。但它只能解决八皇后问题，而不能解决任意的,n,皇后问题。,check2(,int,a,int n)/,多次被调用，只是一重循环,int,i;,for,(i=1;in),即表示最后一个皇后摆放完毕，输出结果,;else,for(i=,下界,;i0(,有路可走,)and(,未达到目标,)/,还未回溯到头,if(i=n),搜索到一个解，输出,;/,搜索到叶结点,else /,正在处理第,i,个元素,ai,第一个可能的值；,while(ai,不满足约束条件且在搜索空间内,),ai,下一个可能的值；,if(ai,在搜索空间内,),标识占用的资源,;i=i+1;/,扩展下一个结点,else ,清理所占的状态空间；,i=i-1;/,回溯,