高级回溯讨论 估计回溯算法的平均效率 确定子结点的排列规则 计数搜索树中平均遍历的结点 子集树和排列树 Monte carlo方法 装载问题(01背包)问厦都是子集树 1.从根开始,随机选择一条路经,直到不能分 皇后问题与旅行售货员问题是排列树 依次对x赋值 估计回溯算法的平均效率 的值是从当时的5中随机选取,直到向量不能 张为止 判断是否满足多米诺性质 2.假定搜索树的其他|5-1个分支与以上随机选 ■搜索策略-深度优先 出的路径一样,计数搜索树的点数。 确定每个结点能够分支的约束条件 3.重复步骤1和2,将结点数进行概率平均 ■确定存储搜索路径的数据结构 算法 计算结点数 Monte carlo m为本次取样结点总数,k为层数,八为本层分支数 n2为上层分支数,为树的层数 2. for i 1 to t do ∥取样次数 m=1;r2=1;k=1 While k<=n do m= Estimate(n)∥m为本次结总数 3 if sk= then return m 5. sum/= t ←随机选择sk的元素 回滴算法 例 Monte Carlo方法估计四后问题的效率 必要条件一多米诺性质 case3.<1,3>:1+4X1+4X2=13 假设4抽样测试:case11次,case21次,cse32次,平均为16 设尺(x1,2,…,)为真表示向量<x1,x2,…,加中个皇 解空间的蝻点败为17 后放量在彼此不能攻击的位 M+1)→尺Ⅺ,…,冰)0<k<n回溯算法 37 高级回溯讨论 „ 确定子结点的排列规则 „ 子集树和排列树 „ 装载问题(0-1背包)问题都是子集树 „ 皇后问题与旅行售货员问题是排列树 „ 估计回溯算法的平均效率 „ 判断是否满足多米诺性质 „ 搜索策略----深度优先 „ 确定每个结点能够分支的约束条件 „ 确定存储搜索路径的数据结构 回溯算法 38 估计回溯算法的平均效率 „ 计数搜索树中平均遍历的结点 „ Monte Carlo方法： 1．从根开始，随机选择一条路经，直到不能分 支为止, 即从x1,x2,…, 依次对xi赋值，每个xi 的值是从当时的Si中随机选取，直到向量不能 扩张为止 2．假定搜索树的其他|Si|-1个分支与以上随机选 出的路径一样，计数搜索树的点数。 3．重复步骤1和2，将结点数进行概率平均。 回溯算法 39 算法 Monte Carlo 1.sum = 0 2.for i = 1 to t do //取样次数 t 3. m = Estimate(n) //m为本次结总数 4. sum+= m 5.sum /= t 回溯算法 40 计算结点数 m为本次取样结点总数，k 为层数，r1为本层分支数, r2为上层分支数，n为树的层数 Estimate(n) 1. m=1;r2=1;k=1 2. While k<=n do 3. if Sk = then return m 4. r1 = |Sk|*r2 5. m = m + r1 6. 随机选择Sk的元素 7. r2 = r1 8. k++ ∅ xk ← 回溯算法 41 „ 例 Monte Carlo方法估计四后问题的效率 case1．<1,4,2>：1+4+4×2+4×2 = 21 case2．<2,4,1,3>:：4×3+1=17 case3．<1,3>：1+4×1+4×2=13 假设4次抽样测试：case1 1次，case2 1次，case3 2次，平均为16 解空间的结点数为17 回溯算法 42 必要条件—多米诺性质 „ n皇后问题 „ 设P(x1, x2, …, xi) 为真, 表示向量<x1,x2, …,xi>中i个皇 后放置在彼此不能攻击的位置 P(x1 , x2 ,..., xk+1 ) → P(x1 , x2 ,..., xk ) 0 < k < n