算法第5盏穆回溯法.ppt

* 5.13 回溯法效率分析 通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素： 产生x[k]的时间； 满足显约束的x[k]值的个数； 计算约束函数constraint的时间； 计算上界函数bound的时间； 满足约束函数和上界函数约束的所有x[k]的个数。 好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。 选择约束函数时, 通常存在生成结点数与约束函数计算量之间的折衷。 * 重排原理 在有哪些信誉好的足球投注网站试探时，选取x[i]的值顺序是任意的。在其它条件相当的前提下，让可取值最少的x[i]优先。 下图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。 图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组(叶结点)。对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。 前者的效果明显比后者好。 (a) (b) * 估计回溯算法的结点数目和平均效率 －－蒙特卡罗方法 主要思想:在解空间树上产生一条随机的路径,并沿此路径估算解空间树中满足约束条件的结点总数. Monte Carlo方法的算法步骤: 1．从根开始，随机选择一条路经，直到不能分支为止, 从x1, x2, …, 依次对xi赋值，每个xi的值是从当时的路径中随机选取，直到向量不能扩张为止. 2．假定有哪些信誉好的足球投注网站树的其他分支与以上随机选出的路径一样，计算有哪些信誉好的足球投注网站树的结点数。 3．重复步骤1和2，将结点数进行概率平均。 * 算法Monte Carlo 1．sum?0; //sum为t次结点平均数 2．for i?1 to t do //取样次数t 3. m?Estimate(n); //m为本次结点总数 4. sum?sum+m; 5. sum?sum/t; * m为本次取样结点总数，k为层数，r为本层分支数, n为树的层数, mi为第i层满足约束条件的结点数. 算法Estimate(n) //估算回溯法生成的结点数 1. m?1; r?1; k?1; 2. While k ? n do 3. SetType T = x[ k ]//满足约束的可取值集合； 4. if T = ? then return m; 5. r?|T|*r; 6. m?m+r; 6. x[k]?随机选择T的元素； 7. k?k+1; 回溯法生成的满足约束条件的结点总数：1+m0+m0m1+m0m1m2+… * Monte Carlo方法估计四后问题的效率 1,4,2：1+4+4?2+4?2*1 = 21 1+m0+m0m1+m0m1m2+… * 回溯法小结 （1）回溯法的实质是检测所有可能的解，也就是穷尽所有的可能情况，从中寻求问题的答案。因此，其时间复杂度与穷尽法相同。 在人工智能中应用回溯法求解时，要用启发信息、启发函数来判断每一个可能的动作，按其函数值的大小将所有可能的动作排成一列。 * 把导致成功可能性大的动作排在前面，于是很可能很快就得到了问题的答案。但回溯法提供了一种规律性求解的方法，一般说来，时间复杂度是比较高的。 （2）回溯法可以用来求一个解，也可以用来求出所有的解。 * 课后作业 第三版：算法分析题：5-3，5-5 算法实现题（作为分析题）：5-4，5-13，5-18 第四版：算法分析题：5-3，5-5 算法实现题（作为分析题）：5-4，5-13，5-18 * 习题5-3 0-1背包问题的最优解 重写0-1背包问题的回溯法, 使算法运行结束后能输出最优解. 提示: 为构造最优解, 需在算法中记录与当前最优值相应的当前最优解. 因此, 可在类Knap中2个私有成员x和bestx, 分别用于记录从根至当前结点的路径和当前最优解. * 实现题5-4 运动员最佳配对问题。一个羽毛球队有男女运动员各n人，给定2个n*n矩阵P 和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打时的竞赛优势； Q[i][j]则是女运动员i和男运动员j配合时的竞赛优势。显然，由于技术的 配合和心理状态等各种因素的影响，P[i][j]不一定等于Q[i][j]。设计一个 算法，计算出男女运动员的最佳配对法，使各组男女双方竞赛优势乘积达到 最大。 提示: 解空间为一棵排列树, 可套用有哪些信誉好的足球投注网站排列树的回溯法框架. * 实现题5-13 :工作分配问题。设有n件工作要分配给n个不同的人去完成。将工作i分配给第j个人所需要花费的费用为Cij。设计一个算法，为每个人都分配