回溯法求解N皇后问题.ppt

1、8.1.3 回溯法的求解过程,由于问题的解向量X=(x1, x2, , xn)中的每个分量xi(1in)都属于一个有限集合Si=ai1, ai2, , airi，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1S2Sn中的元素。 初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。依此类推，一般情况下，如果X=(x1, x2, , xi)是问题的部分解，则选择S

2、i+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：,（1）如果X=(x1, x2, , xi1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； （2）如果X=(x1, x2, , xi1)是问题的部分解，则继续构造解向量的下一个分量； （3）如果X=(x1, x2, , xi1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况： 如果xi+1= ai1k不是集合Si1的最后一个元素，则令xi+1= ai1k1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； 如果xi+1= ai1k是集合Si1的最后一个元素，就回溯到X

3、=(x1, x2, , xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik1；否则，就继续回溯到X=(x1, x2, , xi1)；,8.3.1 八皇后问题,八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在88的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在nn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。,若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上斜率为-1的斜线

4、上，满足条件ij= xjxi ，在棋盘上斜率为1的斜线上，满足条件ij= xixj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件： |i j | xi xj| （式8.2）,显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，n皇后问题的可能解用一个n元向量X=(x1, x2, , xn)表示，其中，1in并且1xin，即第i个皇后放在第i行第xi列上。 由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件： xixj （式8.1）,为了简化问题，下面讨论四皇后问题。 四皇后问题的解空间树是一个完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结

5、点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,(a) (b) (c) (d) (e),(f) (g) (h) (i) (j),Q,Q,Q,回溯法求解4皇后问题的搜索过程,算法的实现,假设回溯法要找出所有的答案结点 。 设(x1,x2,xi-1)是状态空间树中由根到一个结点的路径，而T(x1,xi-1)是下述所有结点xi的集合，它使得对于每一个xi，(x1,x2,xi)是由根到一个结点xi的路径；假定还存在着一些限界函数Bi，如果路径(x1,x2

6、,xi)不可能延伸到一个答案结点，则Bi(x1,x2,xi)取假值，否则取真值。 于是解向量X(1:n)中的第i个分量，就是那些选自集合T (x1,x2,xi-1)且使Bi为真的xi,算法8.4：可以放置一个新皇后吗？,Procedure PLACE(k) /如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。X是一个全程数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/ global X(1:k); integer i,k; i1 while ik do if X(i)=X(k) or ABS(X(i)-X(k)=ABS(i-k) then return

7、 (false) end if ii+1 repeat return (true) End PLACE,判断是否有其它的皇后与之在同一列或同一斜对角线上,算法8.5：n-皇后问题的解,Procedure NQUEENS(n) /此过程使用回溯法求出一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置/ integer k,n,X(1:n) X(1)0 ; k1 / k是当前行；X(k)是当前列 / while k0 do / 对所有的行，执行以下语句 / X(k)X(k)+1 /移到下一列/ while X(k)=n and Not PLACE(k) do /此处能放这个皇后吗/ X(k)X(k)+1 /不能放则转到下一列/ repeat if X(k)=n then /找到一个位置/