8算法第八章回溯法解读.ppt

8.2 8-皇后问题 问题分析 限界函数 求n-皇后问题的所有解 效率分析 问题分析 在n-皇后问题中，(x1,x2,..xn)表示一个解，xi表示第i个皇后放在第i行的列数。 不同行 不同列 不同对角线 (x1,x2,..xn) x1,x2,..xn互不相同 ？ a11 a12 a13 a14 a15 a16 a17 a18 a21 a22 a23 a24 a25 a26 a27 a28 a31 a32 a33 a34 a35 a36 a37 a38 a41 a42 a43 a44 a45 a46 a47 a48 a51 a52 a53 a54 a55 a56 a57 a58 a61 A62 a63 a64 a65 a66 a67 a68 a71 a72 a73 a74 a75 a76 a77 a78 a81 a82 a83 a84 a85 a86 a87 a88 同一条斜角线上的每个元素 由左到右具有相同的“行-列”值; 由右到左具有相同的“行+列”值。 限界函数分析 用二维数组A(8,8)的下标来标记每个皇后的位置； 对于同一条斜角线上的每个元素 由左到右具有相同的“行-列”值; 由右到左具有相同的“行+列”值。 设有两个皇后位于(i,j)和(k,l)位置上 i-j=k-l i+j=k+l j-l=i-k j-l=k-i |j-l|=|i-k| 限界函数PLACE(k) // 前k-1行的皇后已经放置，现在确定第k行皇后欲放在X(k)列上，是否可以？ PLACE(k) 令X(k)与X(i)逐个比较，i=1..k-1。 若存在X(k)=X(i)或者|X(i)-X(k)|=|i-k| 则返回false； 否则返回true。 相当于两个皇后位于(i,X(i))和(k,X(k))位置上。 算法8.4 能否放置一个新皇后？ procedure PLACE(k) int i , k i←1 while ( ik ) do if (X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k)) then return (false) endif i ← i+1 repeat return (true) end PLACE 若一个皇后能放在第k行和第X(k)列, 则返回true, 否则返回false。 X是全程数组, 进入此过程时已置入了k个值, ABS是绝对值函数。 // 若两个皇后在同一列上, 或在 同一对角线上, 则说明该位置 不能放皇后, 应返回false值 算法8.5求n-皇后问题的回溯算法描述——求所有解 procedure NQUEENS(n) int k, n, X(1:n) X(1) ← 0 ; k ← 1 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 if(k=n) then print (X) else k ←k+1; X(k) ←0 endif else k ←k-1; endif repeat end NQUEENS 当前列X(k)不能放皇后k时，放到下一列。 若是一个完整的解，则打印数组X。 否则转到下一行，准备求解下一个皇后。 没有合适的位置, 回溯。 1 2 3 4 X 1 3 0 Q1 Q2 k=3; while (k0) do { X(k)=X(k)+1; while (X(k)≤n and not PLACE(k)) do if (X(k)≤n) then 不执行 else k=k-1=2; //回溯 } end while 1≤n and not false , X(k)=X(k)+1=2; 2≤n and not false , X(k)=X(k)+1=3; 1 3≤n and not false , X(k)=X(k)+1=4; 4≤n and not false , X(k)=X(k)+1=5; 2 3 4 5 5n , 循环不执行 Q3 Q3 Q3 Q3 k=2; while (k0) d