分支限界法实验最优装载问题.pdf

【最优装载问题与分支限界法】 最优装载问题是一个经典的组合优化问题，旨在寻找最佳的装载方案，使得一组集装箱能够合理地分配到两艘载重量有限的轮船上，以达到最大的装载重量。在这个问题中，每艘轮船的载重量分别为C1和C2，而每个集装箱有其特定的重量Wi。目标是确定是否存在一种装载方法，可以将所有集装箱装上这两艘船，并找到这样的装载方案。 **实验目的** 1. 理解并掌握分支限界法的原理，学习如何运用队列解决最优装载问题。 2. 实践中通过实现分支限界法来解决最优装载问题，锻炼问题解决能力。 **实验原理** 最优装载问题可以通过分支限界法求解。该方法基于广度优先搜索（BFS），使用一个队列存储待处理的结点。算法的核心思路如下： 1. 先尝试尽可能填满第一艘船。 2. 将剩下的集装箱装载到第二艘船上。 **算法流程** 1. 初始化活结点队列Q，将起始结点（表示未装载任何集装箱的状态）加入队列。 2. 在循环中，每次取出队列头部的结点作为当前扩展结点。 3. 检查当前结点的左儿子（表示将当前集装箱装载到第一艘船）是否为可行结点，如果可行则加入队列。 4. 检查右儿子（表示将当前集装箱装载到第二艘船），若其可行且优于当前最优解，也加入队列。 5. 如果当前结点是该层的最后一个结点，更新剩余集装箱的重量，进入下一层。 6. 当队列为空或到达目标状态时，算法结束。 **关键代码** ```cpp void Maxloading(int w[], int c, int n, int bestx[]) { // 初始化队列，添加初始结点 queue<QNode*> Q; Q.push(0); // 搜索子集空间树 while (true) { // 处理左儿子和右儿子结点 // ...（省略部分代码） // 更新剩余集装箱重量，进入下一层 if (Q.empty()) break; Q.push(0); E = Q.front(); Q.pop(); i++; r -= w[i]; } // 构建最优解 // ...（省略部分代码） } ``` **实验心得** 在实际操作中，由于涉及剪枝操作，对问题的理解和细节处理至关重要。特别是在处理每层结束时，需要更新剩余集装箱的重量，这直接影响到右子树是否会被剪掉。因此，对算法逻辑的清晰把握是解决问题的关键。 **总结** 分支限界法是一种有效的解决组合优化问题的方法，它能用于解决最优装载问题，相比于贪心算法，分支限界法能确保找到全局最优解，而不仅仅是局部最优解。通过本次实验，学生不仅能深入理解分支限界法的工作机制，还能提高解决问题的实际编程能力。