分枝限界法详解：装载问题与单源最短路径应用

装载问题-第二十一讲 分枝定界法 装载问题是经典的优化问题，涉及到如何有效地分配有限的运输资源，如两艘轮船的载重量，来装载一系列集装箱。问题的核心是确保所有集装箱的总重量不超过船只的最大载重量，并找到一个可行的装载方案。装载问题可以转化为图论中的问题，例如在有向图中寻找最短路径。 分枝限界法是一种常用的求解组合优化问题的算法，它在问题的解空间树上进行搜索，目标是找到满足约束条件的最优解。与回溯法类似，但有所不同： 1. 目标差异： - 回溯法旨在找到所有满足约束条件的解，而分枝限界法则关注的是找到一个最优解或在满足条件的解中找到最佳选择。 2. 搜索策略： - 回溯法采用深度优先搜索，而分枝限界法可能采用广度优先搜索，或优先处理具有最小耗费（最大效益）的结点。 分枝限界法的基本思想是，以广度优先或最小耗费优先的方式遍历解空间树。每个活结点仅有一次机会扩展为子结点，如果扩展导致不可行或非最优解，则排除，其余子结点加入活结点列表。这一过程持续直至找到所需的解或活结点表为空。 常见的分枝限界法实现包括队列式（按先进先出原则）和优先队列式（根据优先级选取扩展结点）。例如，在单源最短路径问题中，优先队列式分枝限界法利用最小堆来存储结点，堆中的优先级由当前路径长度决定。从源点开始，扩展节点的子节点会被插入堆中，然后取堆中路径最短的结点作为下一轮扩展。 在解决实际问题时，如图所示的单源最短路径问题，通过构建解空间树，每个结点都对应一个路径长度。优先队列式分枝限界法通过不断扩展和检查邻居节点，逐步逼近最短路径，直到找到从源点到目标点的最短路径。 总结来说，装载问题的分枝定界法是一个在优化问题求解中广泛应用的技术，通过智能地搜索和剪枝解空间，寻找满足特定条件的最佳解决方案。这种方法在物流、网络路由等领域都有广泛的应用，并展示了如何将理论算法与实际问题相结合。