八皇后问题详细的解法.ppt

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