清华大学出版社 TSINGHUA UNIVERSITY PRESS 63装载问题 1.问题描述 有一批共个集裝箱要装上2艘载重量分别为C1和C2的轮船,其中集 装箱i的重量为Wi,且 ,≤C1+C 裝载问题要求确定是否有一个合理的装载方案可将这个集装箱装上 这2艘轮船。如果有,找出一种装载方案 容易证明:如果一个给定装载问题有解,则采用下面的策略可得到 最优装载方案。 (1)首先将第一艘轮船尽可能装满; (2将剩余的集装箱裝上第二艘轮船
11 6.3 装载问题 1. 问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集 装箱i的重量为Wi，且 1 2 1 w c c n i i + = 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上 这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到 最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船
清华大学出版社 TSINGHUA UNIVERSITY PRESS 63装载问题 2.队列式分支限界法 在算法的 while循环中,首先检测当前扩展结点的左儿子结点是 否为可行结点。如果是则将其加入到活结点队列中。然后将其右 U子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个 儿子结点都产生后,当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点,由于队列中 每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结 点队列一定不空。当取出的元素是-1时,再判断当前队列是否为 空。如果队列非空,则将尾部标记-1加入活结点队列,算法开始 处理下一层的活结点。 12
12 6.3 装载问题 2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是 否为可行结点。如果是则将其加入到活结点队列中。然后将其右 儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个 儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中 每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结 点队列一定不空。当取出的元素是-1时，再判断当前队列是否为 空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始 处理下一层的活结点
清华大学出版社 TSINGHUA UNIVERSITY PRESS 63装载问题 2.队列式分支限界法 while(true) if(ew+w]<=c) enQueue(ew+w[il,i);∥检查左儿子结点 enQueue(ew, i) ∥右儿子结点总是可行的 ew=( Integer) queue. remove) int value;∥取下一扩展结点 if(ew==-1) i if(queue is Empty) return bestw; queue. put( new Integer(-1)) ∥同层结点尾部标志 ew=( (Integer) queue. remove) int value(;∥取下一扩展结点 ∥进入下一层}} 13
13 6.3 装载问题 2. 队列式分支限界法 while (true) { if (ew + w[i] <= c) enQueue(ew + w[i], i); // 检查左儿子结点 enQueue(ew, i); //右儿子结点总是可行的 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 if (ew == -1) { if (queue.isEmpty()) return bestw; queue.put(new Integer(-1)); // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 63装载问题 3.算法的改进 节点的左子树表示将此集装箱装上船,右子树表示不将此集装箱 装上船。设 best是当前最优解;ew是当前扩展结点所相应的重 量;r是剩余集装箱的重量。则当eW+r≤ best时,可将其右子树 剪去,因为此时若要船装最多集装箱,就应该把此箱装上船。 另外,为了确保右子树成功剪枝,应该在算法每一次进入左子树 的时候更新 best的值
14 6.3 装载问题 3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱 装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重 量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树 剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树 的时候更新bestw的值