1. 基本概念

分支限界算法的策略

当一个节点成为当前扩展节点时：

• 首先列出它的全部孩子节点

• 然后使用剪枝函数，剪去那些无法达到最终状态或最优解的孩子节点，将其余孩子节点加到活结点列表中，并且使用限界函数对它们进行排序

• 选择第一个活结点，使之成为新的扩展节点

分支限界算法和回溯算法的区别

• 分支限界算法以广度优先或最小耗费优先的方式，在解空间中搜索满足约束条件的一个解，并且该解满足限界函数的极值

• 回溯算法以深度优先的方式，在解空间上，搜索满足约束条件的所有解

2. 单源最短路径

在下面的图 G 中，每条边都有一个非负权值，要求求出从源顶点 S 到目标顶点 T 的最短路径：

Python 实现：

tim-chow 的 Github

3. 装载问题

• 问题描述
  将 n 个集装箱装到 2 艘载重量分别为 c₁ 和 c₂ 的轮船中，其中集装箱 i 的重量为 w_i，且 w₁ + w₂ + ... + w_n <= c₁ + c₂
• 基本思路
  尽可能将第一艘轮船装满，如果剩余集装箱的重量之和不大于第二艘轮船的载重量，则可以放下；否则，无法放下
• 目标
  对第一艘轮船的装载进行优化

Python 实现：

tim-chow 的 Github

4. 接雨水 2

• 思路：
  参考接雨水 1：leetcode 42 接雨水
• 实现：
  接雨水 2：leetcode 407 接雨水 2