《八皇后问题详细的解法ppt课件.ppt》由会员分享,可在线阅读,更多相关《八皇后问题详细的解法ppt课件.ppt(23页珍藏版)》请在三一办公上搜索。
1、1,八皇后问题,2,1八皇后问题背景2盲目的枚举算法3加约束的枚举算法4回溯法及基本思想5 回溯法应用6八皇后问题的递归回溯算法7八皇后问题的非递归回溯算法,3,【背景】 八皇后问题是一个以国际象棋为背景的问题: 如何能够在 88 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。,4,八皇后问题,要在8*8的国际象棋棋盘中放8个皇后,使任意两个皇后都不能互相吃掉。规则:皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。八皇后的两组解,5,【问题分析】,设八个皇后为xi,分别在第i行(i=1,2,3,
2、4,8);问题的解状态:可以用(1,x1),(2,x2),(8,x8)表示8个皇后的位置;由于行号固定,可简单记为:(x1,x2,x3,x4,x5,x6,x7,x8);问题的解空间:(x1,x2,x3,x4,x5,x6,x7,x8),1xi8(i=1,2,3,4,8),共88个状态;约束条件:八个(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一对角线上。,原问题即:在解空间中寻找符合约束条件的解状态。,按什么顺序去搜?目标是没有漏网之鱼,尽量速度快。,6,枚举得有个顺序,否则轻则有漏的、重复的;重
3、则无法循环表示。,2 【问题设计】盲目的枚举算法,a 盲目的枚举算法通过8重循环模拟搜索空间中的88个状态;按枚举思想,以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
4、=1;x7=10;x7+) for (x8=1;x8=10;x8+) if (check(x)=0) printf(x); ,该如何解决冲突的问题呢?1.行;我们是按照行枚举的,保证了一行一个皇后;2.列:判断是否存在xi=xj3.对角线:主对角线的i-j与从对角线的i+j存在特殊关系,如图:,9,盲目的枚举算法,约束条件?不在同一列:xixj;不在同一主对角线上:xi-i xj-j;不在同一负对角线上:xi+i xj+j。,违规的情况可以整合改写为:abs(xi - xj)=abs( i-j ) or (xi = xj),10,盲目的枚举算法,queen1( ) int a9; for(a1
5、=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
6、(0); return(1); ,双重循环,任意两个皇后之间都必须检查。,用a1a8存储x1x8,11,有“通用的解题法”之称。回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。,1 回溯法,回溯法指导思想走不通,就掉头。,12,求问题所有解:要回溯到根,且根结点的所有子树都已被搜索遍
7、才结束。求任一解:只要搜索到问题的一个解就可结束。,1 回溯法,13,1 回溯算法设计过程,step1 确定问题的解空间;step2 确定结点的扩展规则;step3 搜索解空间。,14,2 回溯法应用-加约束的枚举算法,如果能够排除那些没有前途的状态,会节约时间;,如何提前发现?,回溯法指导思想走不通,就掉头,如(1,1, x3,x4,x5,x6,x7,x8)没有必要再扩展;,这种状态扩展后会产生86个结点;,同样的(1,2, x3,x4,x5,x6,x7,x8),也应被排除。,在每一次扩展E结点后,都进行检查;,对检查结果如何处理?,检查合格的才继续向下扩展;遇到不合格的“掉头就走”。,只要
8、当前枚举到的状态可行,就继续枚举下去。当找到一种方案或者无法继续枚举下去时,就退回到上一状态。退回到上一状态的过程叫做回溯,枚举下一个状态的过程叫做递归。回溯就是像人走迷宫一样,先选择一个前进方向尝试,一步步试探,在遇到死胡同不能再往前的时候就会退到上一个分支点,另选一个方向尝试,而在前进和回撤的路上都设置一些标记,以便能够正确返回,直到达到目标或者所有的可行方案都已经尝试完为止。,16,2 回溯法应用-例1 b加约束的枚举算法,我们可以依次确定每一行皇后的位置,如果在某一列可以放下一个皇后,我们就在这里放下,并搜索下一行,若无法放下皇后则回到上一行,即回溯,当n行的皇后都已确定后,我们就找到
9、了一种方案,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)
10、/多次被调用,只是一重循环 int i; for(i=1;i=n-1;i+) if (abs(ai-an)=abs(i-n) or (ai=an) return(0); return(1);,19,2 回溯法应用-算法说明,八皇后问题中的核心代码:遍历过程函数;check函数。,解决此类问题的核心内容:解空间树的搜索算法;估值/判断函数:判断哪些状态适合继续扩展,或者作为答案状态。,20,2 回溯法应用-n皇后问题,介绍过的方法:c递归回溯算法;d非递归回溯算法;,策略:能进则进,不能进则换,不能换则退。,21,2 回溯法应用-算法框架-递归算法框架,int an;Queens(int k)
11、if (kn) 即表示最后一个皇后摆放完毕,输出结果; else for(i=下界 ; i=上界; i+) /枚举K个皇后所有可能的路径 依次从列顶端开始搜索,一直到列底端,直到找到合适位置,如果未找到,自动返回上层递归 ak=i; if (check(a,k) /满足限界函数和约束条件,不冲突 /递归摆放下一个皇后Queens (k+ 1); ,22,23,2 回溯法应用-算法框架-非递归回溯框架,int an,i;初始化数组a ;i=1;While (i0(有路可走) and (未达到目标) /还未回溯到头 if (i=n) 搜索到一个解,输出; /搜索到叶结点 else /正在处理第i个元素 ai第一个可能的值; while (ai不满足约束条件且在搜索空间内) ai下一个可能的值; if (ai在搜索空间内) 标识占用的资源; i=i+1; /扩展下一个结点 else 清理所占的状态空间;i=i-1; /回溯 ,