示例2:0/1背包问题 令n=3,w=[20,15,151,p=40,25,25],c=30 FIFO分支定界 E节点活节点表 A BC」 A B B C E FG E G 0解1:10,收益40 K MN( F 解2:[0,1,1,收益50 G NULL 2021/2/6
示例2：0/1背包问题 • FIFO分支定界 ❖ n=3, w=[20,15,15], p=[40,25,25], c=30 E-节点 活节点表 A B C B C E C E F G E F G 解1：[1,0,0], 收益40 F G 解2：[0,1,1], 收益50 G NULL 2021/2/6 6
F|FO分支定界法小结 对于迷宫问题,FIFO法总能找到从入口到出口的最短路 径;而回溯法却不能保证 在解空间树上的FIFO法,类似从根节点出发的BFS方法; ·与BFS的区别在于:在FIFO分支定界中,不可行的节点 不会被搜索! 2021/2/6
FIFO分支定界法小结 • 对于迷宫问题，FIFO法总能找到从入口到出口的最短路 径；而回溯法却不能保证 • 在解空间树上的FIFO法，类似从根节点出发的BFS方法； • 与BFS的区别在于：在FIFO分支定界中，不可行的节点 不会被搜索！ 2021/2/6 7
最大收益分支定界思想 ·使用一个最大堆:其中的E节点按照每个活节点收益值 的降序,或是按照活节点任意子树的叶节点所能获得的 收益估计值的降序从队列中取出 2021/2/6
最大收益-分支定界思想 • 使用一个最大堆：其中的 E-节点按照每个活节点收益值 的降序，或是按照活节点任意子树的叶节点所能获得的 收益估计值的降序从队列中取出 2021/2/6 8
再解示例2:最大收益法 令n=3,w=[20,15,15l,p=40,25,25],c=30 E节点活节点表 A BC」 A B EC B C EC 解1:[1,0,0,收益40 D E C FG H K M(N( F 解2:10,1,1,收益50 GNULL 2021/2/6
再解示例2：最大收益法 E-节点 活节点表 A B C B E C E C 解1：[1,0,0], 收益40 C 解2：[0,1,1], 收益50 G NULL ❖ n=3, w=[20,15,15], p=[40,25,25], c=30 F G F G 2021/2/6 9
最大收益分支定界小结 定界函数确定最大收益的上限;如果一个节点的定界函数 值不大于目前最优解的收益值,则此节点会被删除而不作 为E节点展开 ·节点取出策略:使节点按照它们收益的定界函数值的非升 序从最大堆中取出;这种策略从可能到达一个好的叶节点 的活节点出发,而不是从目前具有较大收益值的节点出发 2021/2/6
最大收益-分支定界小结 • 定界函数确定最大收益的上限；如果一个节点的定界函数 值不大于目前最优解的收益值，则此节点会被删除而不作 为E-节点展开 • 节点取出策略：使节点按照它们收益的定界函数值的非升 序从最大堆中取出；这种策略从可能到达一个好的叶节点 的活节点出发，而不是从目前具有较大收益值的节点出发 2021/2/6 10