0/1背包的分支限界法过程 2.总结 从0/1背包问题的搜索过程可看出:与回溯法相 比,分支限界法可根据限界函数不断调整搜索 方向,选择最可能得最优解的子树优先进行搜 索→找到问题的解
11 0/1背包的分支限界法过程 2. 总结 从0/1背包问题的搜索过程可看出：与回溯法相 比，分支限界法可根据限界函数不断调整搜索 方向，选择最可能得最优解的子树优先进行搜 索→找到问题的解
分支限界法的设计思路 求解最大化问题,解向量为X=(x12…xn),x的取值 范围为S,|S}=r。在使用分支限界搜索问题的解空间 树时,先根据限界函数估算目标函数的界[dowm,p 然后从根结点出发,扩展根结点的r个孩子结点,从 而构成分量x的r种可能的取值方式。 对这个孩子结点分别估算可能的目标函 数 bound(x1),其含义:以该结点为根的子 树所有可能的取值不大于bom(x1),即: 1 8bom(x)≥boml(x1x2)2.≥bom(x1,xn)
12 分支限界法的设计思路 设求解最大化问题，解向量为X=(x1 ,…,xn )，xi的取值 范围为Si，|Si |=ri。在使用分支限界搜索问题的解空间 树时，先根据限界函数估算目标函数的界[down, up]， 然后从根结点出发，扩展根结点的r1个孩子结点，从 而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函 数bound(x1 )，其含义：以该结点为根的子 树所有可能的取值不大于bound(x1 )，即： bound(x1 )≥bound(x1 ,x2 )≥…≥ bound(x1 ,…,xn ) x1 x2 ... x2 r1
分支限界法的设计思路 n岩呈孩子结点的目标函数 值超出目标函数的下界 则将该孩子结点丢弃;否 则,将该孩子结点保存在 是否PT中最大值? 待处理结点表PT中。 ■再取PT表中目标函数极大网x是问题 用X来调整down 值结点作为扩展的根结点,的最优 bound是最少所能 重复上述。 得到的解 ■直到一个叶子结点时的可 「继续搜索 行解X=(x1…xn),及目标 函数值 bound(x1…xn)
13 分支限界法的设计思路 ◼ 若某孩子结点的目标函数 值超出目标函数的下界， 则将该孩子结点丢弃；否 则，将该孩子结点保存在 待处理结点表PT中。 ◼ 再取PT表中目标函数极大 值结点作为扩展的根结点， 重复上述。 ◼ 直到一个叶子结点时的可 行解X=(x1 ,…,xn )，及目标 函数值bound(x1 ,…,xn )。 是 是否PT中最大值？ 否 则X是问题 的最优解； 用X来调整down bound是最少所能 得到的解 继续搜索
单源最短路径问题 向题描述 下面以一个例子来说明单源最短路径问题:在下 图所给的有向图G中,每一边都有一个非负边权。要 求图G的从源顶点s到目标顶点之间的最短路径
14 单源最短路径问题 1. 问题描述 下面以一个例子来说明单源最短路径问题：在下 图所给的有向图G中，每一边都有一个非负边权。要 求图G的从源顶点s到目标顶点t之间的最短路径
单源最短路径问题 向题描述 下图是用优先队列式分支限界法解有向图G的 单源最短路径问题产生的解空间树。其中,每一个结 点旁边的数字表示该结点所对应的当前路长。 4 9○5 ○12 06 g yk 705 6○10 14 p 10 15
15 单源最短路径问题 1. 问题描述 下图是用优先队列式分支限界法解有向图G的 单源最短路径问题产生的解空间树。其中，每一个结 点旁边的数字表示该结点所对应的当前路长