Chapter17分支定界 ■与回溯算法的比较 ■171分支定界的思想 ■172算法的应用 ■货箱装船:FIFO、最大收益 ■旅行商问题:最小耗费 2021/2/6
◼与回溯算法的比较 ◼17.1 分支定界的思想 ◼17.2 算法的应用 ◼货箱装船：FIFO、最大收益 ◼旅行商问题：最小耗费 Chapter17 分支定界 2021/2/6 1
分支定界VS.回溯算法 ■相同点: ■都使用树形结构(子集树或排列树)来组织解空间 不同点: ■回溯算法使用DFS方法来搜索树; 分支定界使用BFS方法或最小耗费方法来搜索树 分支定界的解空间比回溯算法要大得多 当內存容量有限时,回溯法更易成功! 但有时候,分支定界能够找到最优解。 2021/2/6
分支定界 VS. 回溯算法 ◼ 相同点： ◼ 都使用树形结构（子集树或排列树）来组织解空间 ◼ 不同点： ◼ 回溯算法使用DFS方法来搜索树； ◼ 分支定界使用BFS方法或最小耗费方法来搜索树 • 分支定界的解空间比回溯算法要大得多 • 当内存容量有限时，回溯法更易成功！ • 但有时候，分支定界能够找到最优解。 2021/2/6 2
1、算法的思想 对E节点的扩充方式:引入活节点表 【思想】每个活节点有且仅有一次机会变成E节点。当一个 节点变为E节点时,则生成从该节点移动一步即可到达的 所有新节点。在生成的节点中,抛弃那些不可能导出(最 优)可行解的节点,其余节点加入活节点表,然后从表中 选择一个节点作为下一个E节点。 从活节点表中取出所选择的节点并进行扩充,直到找到解或 活动表为空,扩充过程才结束。 2021/2/6
1、算法的思想 对E-节点的扩充方式：引入活节点表 【思想】每个活节点有且仅有一次机会变成E-节点。当一个 节点变为E-节点时，则生成从该节点移动一步即可到达的 所有新节点。在生成的节点中，抛弃那些不可能导出（最 优）可行解的节点，其余节点加入活节点表，然后从表中 选择一个节点作为下一个E-节点。 从活节点表中取出所选择的节点并进行扩充，直到找到解或 活动表为空，扩充过程才结束。 2021/2/6 3
选择E节点的方法 先进先出:活节点表的性质与队列相同 最小耗费或最大收益:每个节点都有一个对应的耗费或 收益 查找一个具有最小耗费的解,则活节点表可用最小堆 来建立 ·搜索一个具有最大收益的解,则活节点表可用最大堆 来构造活节点表 下一个E节点就是满足条件的活节点 2021/2/6
选择E-节点的方法 • 先进先出：活节点表的性质与队列相同 • 最小耗费或最大收益：每个节点都有一个对应的耗费或 收益 • 查找一个具有最小耗费的解，则活节点表可用最小堆 来建立 • 搜索一个具有最大收益的解，则活节点表可用最大堆 来构造活节点表 • 下一个 E-节点就是满足条件的活节点 2021/2/6 4
示例1:迷宫老鼠问题 E节点活节点表 , 1,2 1,3 Step1:(1, 1) Step2:(1,2)(2,1 Step3:(2,1 2 Step4:(1,3) (3,1 Step5:(3, 1) 3 Step6:(3,2) (3,3 Goal:(3, 3) NULL 2021/2/6
示例1：迷宫老鼠问题 （1，2） （2，1） Step1:（1，1） E-节点 活节点表 Step2:（1，2） （2，1） （1，3） Step3:（2，1） （1，3） （3，1） Step4:（1，3） （3，1） Step5:（3，1） （3，2） Step6:（3，2） （3，3） Goal:（3，3） NULL 2021/2/6 5
示例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