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