分支限界法的基本思想 常见的两种分支限界法 (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个结 点为扩展结点。 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高 的结点成为当前扩展结点
6 分支限界法的基本思想 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个结 点为扩展结点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高 的结点成为当前扩展结点
解空间树的动态搜索 (1)回溯求解0/1背包问题,虽剪枝减少了搜索 空间,但整个搜索按深度优先机械进行,是盲目 搜索(不可预测本结点以下的结点进行的如何) (2)回溯求解TSP也是盲目的(虽有目标函数, 也只有找到一个可行解后才有意义)
7 解空间树的动态搜索 （1）回溯求解0/1背包问题，虽剪枝减少了搜索 空间，但整个搜索按深度优先机械进行，是盲目 搜索（不可预测本结点以下的结点进行的如何）。 （2）回溯求解TSP也是盲目的（虽有目标函数， 也只有找到一个可行解后才有意义）
解空间树的动态搜索 分支限界法首先确定一个合理的限界函数,并根据限 界函数确定目标函数的界[dow,up 然后按照广度优先策略遍历问题的解空间树,在某· 分支上,依次搜索该结点的所有孩子结点,分别估算 这些孩子结点的目标函数的可能取值(对最小化问题, 估算结点的down,对最大化问题,估算结点的u)。 如果某孩子结点的目标函数值超出目标函数的界,则 将其丢弃(从此结点生成的解不会比目前已得的更 好),否则入待处理表
8 解空间树的动态搜索 分支限界法首先确定一个合理的限界函数，并根据限 界函数确定目标函数的界[down, up]； 然后按照广度优先策略遍历问题的解空间树，在某一 分支上，依次搜索该结点的所有孩子结点，分别估算 这些孩子结点的目标函数的可能取值（对最小化问题， 估算结点的down，对最大化问题，估算结点的up）。 如果某孩子结点的目标函数值超出目标函数的界，则 将其丢弃（从此结点生成的解不会比目前已得的更 好），否则入待处理表
0/1背包的分支限界法过程 向题描述 容量v=10 物品重()价(价重(vn) 4 40 10 25 4 12 贪心法的解(1,0,0.0),价值为40,可作为01背包的下界
9 0/1背包的分支限界法过程 1. 问题描述 物品 重(w) 价(v) 价/重(v/w) 1 4 40 10 2 7 42 6 3 5 25 5 4 3 12 4 容量w=10 贪心法的解(1,0,0,0)，价值为40，可作为0/1背包的下界
0/1背包的分支限界法过程 2.求解过程 上界υb可用最好情况来代替ub=w*(v∧w1)10*10=100 目标函数的界40,100,一般解空间树中第的各结 点,代表对物1~的选择,可这样定限界函数 ub=V+(W-w) *(vi+/wi+D) 已装入价值剩余容量剩下物品最大单位价值v1/w1 的积 可参考板书视图
10 0/1背包的分支限界法过程 2. 求解过程 上界ub可用最好情况来代替ub=w*(v1/w1)=10*10=100 目标函数的界[40, 100]，一般解空间树中第i层的各结 点，代表对物1~i的选择，可这样定限界函数： ub=V+(W-w)*(vi+1/wi+1) 可参考板书视图 已装入价值 剩余容量 剩下物品最大单位价值vi+1/wi+1 的积