“ F一 所要考察的层 /右儿子结点总是可以的 EnQueue(Q, Ew, best, i, n ;//x0=0 if( QIsEmpty o)return 蜻点尾部标志 Q Delete(Ew) 8,6,2,3],c=12 优先队列式分支限界法解装载问题 搜索顺序 优先级定义为从根结点到活动结点相应 影响回溯时间代价的因素 路径上的载重量再加上剩余货物的重量 搜索空间大小 ■活动结点存储在最大值堆中 搜索树的结构和解的分布 分支定界的方法充分利用了搜索树的结构 和解的分布更快的找到解 能否改变搜索空间的大小呢? 不同的搜索空间 背包问题 ■同样的搜索问题,采取不同的搜索顺序 若干个大小有限制的背包,若干物品的 将会有不同的搜索空间 质量总和和这些包的总容量相同,问这 搜索顺序影响搜索树的结构,不同的搜 些包能否将这些物品全部装走? 索顺序导致剪枝在不同的时候发生 两个背包容量都是5,4个物品的重量分 ■搜索顺序决定剪枝的效果 别是4,3,2 n物品同上,如果有三个背包,容量分别 是6,回溯算法 55 Template <class Type> Type MaxLoading( Type w[], Type c, int n ) { Queue<Type> Q; //活动结点队列 Q.Add(-1); //同层结点尾标志 int i = 1; //当前扩展结点所要考察的层 Type Ew = 0; //扩展结点所相应的载重量 Type bestw = 0; // 当前最优载重量 while(true) { //搜索子空间树 //检查左儿子结点 if( Ew + w[i] <=c ) //x[i] = 1 EnQueue(Q, Ew+w[i], bestw, i, n ); //右儿子结点总是可以的 EnQueue(Q, Ew, bestw, i, n ); //x[i] = 0 Q.Delete(Ew); //取下一扩展结点 if (Ew == -1){ //同层结点尾 if( Q.IsEmpty() ) return bestw; Q.Add(-1); //同层结点尾部标志 Q.Delete(Ew); //取下一扩张结点 i++; //进入了下一层 } } 回溯算法 56 „ w= [ 8 , 6 , 2 , 3 ]，c = 12 J -1 A 1 0 B B C C -1 0 D D E F E F 10 G H 回溯算法 57 优先队列式分支限界法解装载问题 „ 优先级定义为从根结点到活动结点相应 路径上的载重量再加上剩余货物的重量 „ 活动结点存储在最大值堆中 回溯算法 58 搜索顺序 „ 影响回溯时间代价的因素 „ 搜索空间大小 „ 搜索树的结构和解的分布 „ 分支定界的方法充分利用了搜索树的结构 和解的分布更快的找到解 „ 能否改变搜索空间的大小呢？ 回溯算法 59 不同的搜索空间 „ 同样的搜索问题，采取不同的搜索顺序 将会有不同的搜索空间 „ 搜索顺序影响搜索树的结构，不同的搜 索顺序导致剪枝在不同的时候发生 „ 搜索顺序决定剪枝的效果 回溯算法 60 背包问题 „ 若干个大小有限制的背包，若干物品的 质量总和和这些包的总容量相同，问这 些包能否将这些物品全部装走？ „ 两个背包容量都是5，4个物品的重量分 别是4，3，2，1 „ 物品同上，如果有三个背包，容量分别 是6，2，2呢？