8第八章回溯.ppt

* 一旦选定了一种状态空间树结构, 前三种因素对于所要解决的实例没有多大的关系, 只有第四种因素,对于问题的不同实例, 生成的结点数是不相同的。 易知，回溯算法最坏情况下的时间复杂度为O(p(n)2n)或O(q(n)n!)，其中p(n)和q(n)为n的多项式。 由于回溯法对同一问题不同实例在计算时间上出现巨大差异，在n很大时，对某些实例仍然十分有效。 用回溯算法处理一棵树所要生成的节点数，可以用蒙特卡罗方法估算出来。 效率估计 * 效率估计---估计满足Bi的X(k)的数目 蒙特卡罗方法 在状态空间树中生成一条随机路径。 设X是这条路径上第i级的一个结点。 在结点X处用限界函数确定没受限界的儿子结点数目mi，在这mi个儿子结点中随机选择一个结点作为这条路径上的下一个结点。 这条路径在以下结点处结束：或者它是一个叶子结点，或者该结点的所有儿子结点都已被限界。 用这些mi可以估算出这棵状态空间树中不受限界结点的总数m。 * 效率估计---估计满足Bi的X(k)的数目 蒙特卡罗方法 优点： 找到所有答案结点的情况非常有用， 限界函数固定不变，计算方便，对状态空间树中同一级结点都适用。 缺点： 只求一个解时，生成的结点数远小于m， 随着检索的进行，限界函数应该更强，使得m的值更小。 * 效率估计 Procedure ESTIMATE //程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数// m ?1; r ?1; k ?1 loop Tk ?{X(k):X(k) ? T(X(1), …,X(k-1) ) and Bk (X(1), …,X(k-1))} if SIZE(Tk)=0 then exit endif r ?r?SIZE(Tk) m ?m+r X(k) ?CHOOSE(Tk) k ?k+1 repeat return(m) end ESTIMATE //第k级的结点数 //从Tk中随机地挑选一个元素 //前第k级的结点总数 返回集合Tk的大小 * 回溯法求解问题的基本步骤 为所求问题定义解空间，使其包含所有  解； 确定适于有哪些信誉好的足球投注网站的解空间结构； 用深度优先方法有哪些信誉好的足球投注网站该解空间，在有哪些信誉好的足球投注网站 过程中利用限界函数避免无效有哪些信誉好的足球投注网站。 * 8.2 8-皇后问题 问题描述及分析 限界函数 求n-皇后问题的所有解 效率分析 * 8.2 8-皇后问题 问题描述: 在一个8*8棋盘上放置8个皇后, 使得每两个皇后之间都不能互相“攻击”, 即每两个皇后都不能在同一行、同一列及同一条斜角线上 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 8皇后问题可以表示为8-元组(x1, …, x8) ,其中xi是放置皇后i所在的列号 图中的可行解表示为一个8-元组 即(4, 6, 8, 2, 7, 1, 3, 5) * 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(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| 时( 即两个皇后所在位置的行差距 等于列差距时), 两个皇后在同一条斜角线上 * 限界函数 PLACE(k)： 令X(k)与X(i)逐个比较，i=1..k-1。 若存在X(k)=X(i)或者|X(i)-X(k)|=|i-k| 则返回false； 否则返回true。 对X(k)的限定 * procedure PLACE(k) int i , k; i?1; while ( ik ) do if (X(i)=X(k) or ABS