页数:47页文件大小:299.9 KB来源: 计算机算法设计与分析ppt课件
本课件讲解回溯法,从解空间的n-元组表示、显式与隐式约束出发,说明解空间树与状态空间树的术语和结点生成方式,给出BACKTRACK与RBACKTRACK的形式化描述、效率估计与蒙特卡罗方法,并以8-皇后问题完整演示限界函数与搜索过程。
第八章回溯
入口8.1一般方法
例8.2子集和数问题
子集和数问题的描述
子集和数问题的描述--另一种表示
解空间的树结构
例8.3n-皇后问题
回溯法在求问题的所有解时,要遍历树才能结束。
解空间树(状态空间树)的术语
问题状态的生成
8x2= 3
13x2= 415x4=3
131x4=3
从根结点出发,以深度优先方式搜索整个解空间。
回溯算法的形式化描述
回溯算法的形式化描述 procedure BACKTRACK(n)int k, n; local X(1: n);k←1; while (k>0) doif(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1)) andB(X(1)…X(k))=TRUE ) then if (X(1) …X(k))是一条抵达答案结点的路径) then print ( X(1)…X(k) ); endifk←k+1; else k←k-1; endif repeat end BACKTRACK//回溯//打印数组X//考虑下一个集合在X(1)…X(k-1)已经被确定的情况下,T(X(1)…X(k-1))给出X(k)的所有可能的取值,限界函数B(X(1)…X(k))判断哪些X(k)满足隐式约束条件
131513211981416 procedure BACKTRACK(n)int k, n local X(1: n)k←1 while (k>0) doif(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1))and B(X(1)…X(k))=TRUE) then if (X(1) …X(k))是一条抵达答案结点的路径) then print ( X(1)…X(k)) endifk←k+1 else k←k-1 endif repeat end BACKTRACKk=2k=3k=4若只需要一个解,怎样修改算法?
procedure RBACKTRACK(k) global X(1:n);int k, n;for(满足下式的每个X(k),X(k)∈T(X(1)…X(k-1))and B(X(1),…B(k))=true)do{ if(X(1),…,X(k))是一条抵达答案结点的路径 then print (X(1)…X(k)); call RBACKTRACK(k+1);} end RBACKTRACK 回溯算法的递归描述进入算法时,解向量X中的前k-1个分量X(1) …X(k-1)已经被赋值对于所有可以由根结点到达,并可能使限界函数B为真的结点X(k),判断(X(1)…X(k))是否是一条能抵达答案结点的路径效率估计
效率估计---估计满足Bi的X(k)的数目
效率估计---估计满足Bi的X(k)的数目
效率估计Procedure ESTIMATE//程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数//m←1; r←1; k←1 loopTk←{X(k):X(k)∈T(X(1), …,X(k-1)) andBk(X(1), …,X(k-1))}ifSIZE(Tk)=0 then exit endifr←r×SIZE(Tk)m←m+rX(k)←CHOOSE(Tk)k←k+1 repeat return(m) end ESTIMATE//第k级的结点数//从Tk中随机地挑选一个元素//前第k级的结点总数返回集合Tk的大小回溯法求解问题的基本步骤
8.2 8-皇后问题
a18a17a16a15a14a13a12a11a28a27a26a25a24a23a22a21a38a37a36a35a34a33a32a31a48a47a46a45a44a43a42a41a58a57a56a55a54a53a52a51a68a67a66a65a64a63A62a61a78a77a76a75a74a73a72a71a88a87a86a85a84a83a82a81用二维数组A(1:8,1: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|时(即两个皇后所在位置的行差距等于列差距时),两个皇后在同一条斜角线上
限界函数
procedure PLACE(k)int i , k;i←1; while ( i<k ) doif(X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k)) then return (false); endifi←i+1; repeat return (true); end PLACE若一个皇后能放在第k行第X(k)列,则返回true,否则返回falseX是全程数组,进入此过程时已置入了k个值, ABS是绝对值函数能否放置一个新皇后的算法描述:注:两个皇后被放置在(i, j)和(k, l)位置上所以j=X(i),l=X(k),|j-l| = |i-k|即为ABS(X(i)-X(k))=ABS(i-k)//若两个皇后在同一列上,或在同一对角线上,则说明该位置不能放皇后,应返回false值
求n-皇后问题的回溯算法描述 procedure NQUEENS(n)int k, n, X(1:n);X(1)←0 ; k←1; while (k>0) doX(k)←X(k)+1; while (X(k)≤nandNot PLACE(k)) doX(k)←X(k)+1; repeat if (X(k)≤n) then if (k=n) then print (X); else { k←k+1; X(k)←0; } endif elsek←k-1; endif repeat end NQUEENS//若是一个完整的解则打印数组X//k是当前行; X(k)是当前列//对所有的行执行循环语句//移到下一列当该位置不能放皇后时转到下一列//找到一个位置//否则转到下一行//没有合适的位置,回溯43210X01Q1PLACE(1)i=1; while ( i<k ) do1<1 ,循环不执行 return (true);X(1)=0 ; k=1; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not true ,循环不执行 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=2; X(2)=0; }} end whilek=2; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not false ,X(k)=X(k)+1=3;3≤n and Not true ,循环不执行123 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }0} end whileQ2PLACE(2)i=1; while ( i<k ) doif(X(i)=X(k)) then return (false);PLACE(2)i=1; while ( i<k ) doif(|X(i)-X(k)|=|i-k|) then return (false);PLACE(2)i=1; while ( i<k ) do{ if(X(i)≠X(k) or|X(i)-X(k)|≠|i-k|) then不执行i=i+1=2;结束循环} return (true);4321031XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)≮n) then不执行 elsek=k-1=2;//回溯} end whilek=2; while (k>0) do{ X(k)=X(k)+1=3+1=4; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not false ,X(k)=X(k)+1=3;4≤n and Not true ,循环不执行 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }} end whileQ213≤n and Not false ,X(k)=X(k)+1=4;4≤n and Not false ,X(k)=X(k)+1=5;2345405≮n ,循环不执行4321041XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)<n) then if (k≠n) then不执行 else { k=k+1=4; X(4)=0;} end whilek=4; while (k>0) do{ X(k)=X(k)+1=1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not true ,循环不执行;} end whileQ2120Q31≤n and Not false ,X(k)=X(k)+1=2;1232≤n and Not true ,X(k)=X(k)+1=3;43≤n and Not true ,X(k)=X(k)+1=4;54≤n and Not true ,X(k)=X(k)+1=5;5≮n ,循环不执行 if (X(k)≮n) then不执行 elsek=k-1=3;//回溯4321241XQ1k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)≮n) then不执行 elsek=k-1=2;//回溯} end whilek=2; while (k>0) do{ X(k)=X(k)+1=4+1=5; while (X(k)≤n and Not PLACE(k)) do} end whileQ23≤n and Not false ,X(k)=X(k)+1=4;4≤n and Not false ,X(k)=X(k)+1=5;3455≮n ,循环不执行55≮n ,循环不执行 if (X(k)≮n) then不执行 elsek=k-1=1;//回溯43211XQ2k=1; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do} end whilek=2; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do2≤n and Not true ,循环不执行;1≤n and Not false ,X(k)=X(k)+1; if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }} end while if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=2; X(2)=0; }2≤n and Not false ,X(k)=X(k)+1;3≤n and Not false ,X(k)=X(k)+1;4≤n and Not true ,循环不执行;20Q1Q212344321042XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do} end whilek=4; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not true ,循环不执行;3≤n and Not true ,循环不执行 if (X(k)≤n) then if (k=n) then print(2,4,1,3)} end whileQ21 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=4; X(4)=0; }1≤n and Not false ,X(k)=X(k)+1;2≤n and Not false ,X(k)=X(k)+1;Q3Q43≤n and Not true ,循环不执行03估算NQUEENS所生成结点数
12345854321+8+8*5+8*5*4+8*5*4*3+8*5*4*3*2=164912345678642111=1401这5次试验的平均值是1625不受限节点的估计数大约是8-皇后状态空间树的节点总数的1625/69281=2.34%8-皇后问题的不受限节点的估计值
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}