背包问题-分支限界法求解

• 此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
• 所用教材：北京大学屈婉玲教授《算法设计与分析》
• 课程资料：https://www.icourse163.org/course/PKU-1002525003
• 承诺不用于任何商业用途，仅用于学术交流和分享
• 更多内容请关注许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/

1. 分支限界法的基本概念与背包问题实例 （10.2）

1.1 组合优化问题的基础概念

组合优化问题涉及在有限的解空间内，找到满足某种约束条件的最优解。
这些问题通常出现在资源分配、路径规划和背包问题等场景中。

• 目标函数：用于描述我们希望最大化或最小化的属性（如最大化背包的价值、最小化路径长度等）。

  • 最大化问题示例：最大化装入背包的物品总价值。
  • 最小化问题示例：寻找最短路径覆盖所有城市。

• 约束条件：限定了可行解的条件。例如，背包问题中，物品总重量不能超过背包容量。

• 可行解：在所有解中，满足约束条件的解称为可行解。

  • 示例：对于一个背包问题，总重量小于等于背包容量的物品组合就是可行解。

• 最优解：在可行解中，使目标函数达到最大值（最大化问题）或最小值（最小化问题）的解。

  • 示例：在可行解中，选出价值最大的物品组合。

1.2 背包问题示例分析

背包问题是一个典型的组合优化问题，其求解过程涉及如何合理地选择物品，以便在满足约束条件的前提下，使物品的总价值达到最大。

示例

• 目标函数：
  $$\max x_1+3x_2+5x_3+9x_4$$
  其中，$x_1,x_2,x_3,x_4$ 分别表示是否选择物品1、2、3、4。

• 约束条件：
  $$2x_1+3x_2+4x_3+7x_4\le 10$$
  每个物品的重量受限于背包的最大容量10。

• 解的表示：

  • $x_i=1$：选择物品 $i$；
  • $x_i=0$：不选择物品 $i$。

示例求解过程：

1. 选择物品1：总重量为 2，价值为 1。
2. 选择物品2和3：总重量为 $3+4=7$，价值为 $3+5=8$。
3. 验证可行性：若当前选择使得重量小于等于10，则该组合为可行解。

1.3 代价函数的定义与性质

代价函数是一个估计函数，用于衡量当前节点及其子树中的解的上界（或下界）。
代价函数有助于在搜索过程中剪枝，即提前判断某些分支是否值得继续探索。

• 代价函数的计算位置：
  每当搜索到一个节点时，都会计算该节点的代价函数值。

• 代价函数的意义：

  • 极大化问题：代价函数的值是该节点为根的子树中可行解的最大可能值。
  • 极小化问题：代价函数的值是该子树中解的最小可能值。

代价函数的性质：

• 极大化问题：父节点的代价函数值应不小于所有子节点的代价函数值。
• 极小化问题：父节点的代价函数值应不大于所有子节点的代价函数值。

3. 代价函数的剪枝：如果节点A的代价函数值已低于当前最优解，则可以立即停止搜索。

1.4 界（Bound）的概念与更新

什么是界？

• 界的定义：
  界是当前已找到的最优解的目标函数值。对于极大化问题，界是最大值；对于极小化问题，界是最小值。

• 界的作用：
  在搜索过程中，界用于判断是否继续探索某条分支。如果当前节点的代价函数值低于界，则该节点无需继续搜索，因为它无法提供更好的解。

界的初始值：

• 极大化问题：初始界设为 0。
• 极小化问题：初始界设为无穷大。

1.5 背包问题实例分析

1.5.1 问题描述与建模

• 物品数量： 4 种物品。
• 物品价值： $v_1=1,v_2=3,v_3=5,v_4=9$。
• 物品重量： $w_1=2,w_2=3,w_3=4,w_4=7$。
• 背包容量： 10。

目标：
选择装入背包的物品，使得总重量不超过 10 的前提下，总价值最大化。

目标函数：

$$\max x_1+3x_2+5x_3+9x_4$$

约束条件：

$$2x_1+3x_2+4x_3+7x_4\le 10,x_i\in \mathbb{N},i=1,2,3,4$$

1.5.2 代价函数的设定

• 代价函数用于估计在剩余背包容量内可以达到的最大价值，并指导搜索树的剪枝。
• 对结点 $<x_1,x_2,...,x_k>$ , 估计以该结点为根的子树中可行解的上界。

1. 单位重量价值的排序：
   计算每个物品的单位重量价值 $v_i/w_i$：

   • $9/7,5/4,3/3,1/2$
   • 排序后：4号物品 > 3号物品 > 2号物品 > 1号物品。
   • 即排在前面的物品单位价值更高，而排在后面的物品，单位价值更低
     

2. 代价函数公式：

   $\Delta$ 是代价函数的关键部分，用于估计背包中剩余容量的最大利用潜力。
   $$F(x)=\text{已装入价值}+\Delta$$

   • 已装入价值：代表当前已选物品所贡献的总价值。
   • $\Delta$：表示剩余背包空间的最大潜在价值。

• 公式：
  $$\Delta =\text{背包剩余重量}\times \frac{v_{k+1}}{w_{k+1}}$$

  • 背包剩余重量：
    这是从当前节点开始，背包还能装入的最大剩余容量，即 $b-{\sum }_{i=1}^k{w}_i\cdot x_i$。

  • $\frac{v_{k+1}}{w_{k+1}}$：
    表示单位重量价值最高的物品。按物品的单位重量价值从高到低排序，确保优先装入高价值的物品，最大化潜在收益。

• 特殊情况：

  • 如果剩余空间足够大，则继续装入单位重量价值最高的物品，计算出 $\Delta$ 的上界。
  • 如果没有物品能够再装入背包，则 $\Delta =0$，即无法进一步增加价值。

  对于某个节点 $⟨x_1,x_2,\dots ,x_k⟩$，即前 $k$ 种物品已经做出选择，剩余的 $n-k$ 种物品还未决定是否装入。代价函数的表达式如下：

$$F(x)=\sum _{i=1}^k{v}_i\cdot x_i+\left(b-\sum _{i=1}^k{w}_i\cdot x_i\right)\cdot \frac{v_{k+1}}{w_{k+1}}$$

• 第一部分： ${\sum }_{i=1}^k{v}_i\cdot x_i$
  已经装入的物品的总价值。

• 第二部分： $\left(b-{\sum }_{i=1}^k{w}_i\cdot x_i\right)\cdot \frac{v_{k+1}}{w_{k+1}}$
  估计剩余重量所能达到的最大价值。这里的 $k+1$ 表示下一个物品，它具有最高单位重量价值 $v_{k+1}/w_{k+1}$。

代价函数的计算逻辑

1. 排序物品：
   将所有物品按 单位重量价值 $v_i/w_i$ 从大到小排序。排序后的物品优先尝试装入，以保证在剩余空间内最大化背包的价值。

2. 剩余空间的估计：
   假设背包剩余的空间为 $b-{\sum }_{i=1}^k{w}_i\cdot x_i$。如果剩余空间足够大，可以装入单位重量价值最高的物品。

3. 剩余价值的估计：

   • 如果剩余空间允许，将其完全用单位价值最高的物品填充。即乘以 $v_{k+1}/w_{k+1}$，得到剩余空间的价值上界。
   • 若剩余空间不够放入任何物品，则第二项为 0。

1.5.3 背包问题的分支限界法实例推导过程

1.5.3.1 决策树的推导过程分析

本次推导采用深度优先搜索（DFS）与代价函数相结合的方式，在搜索树中动态计算每个节点的价值上界，确保高效剪枝。我们从根节点开始依次装入物品，逐步计算背包的剩余容量和价值，根据状态判断是否继续探索或进行剪枝。

在背包问题中，每层的节点代表对某个物品的选择，即装入一定数量的该物品或不装入。随着搜索的进行，剩余容量逐渐减少，代价函数为每条路径提供一个潜在的价值上界，当上界不如当前的最佳解时，立即剪枝。

1.5.3.2 推导过程详细分析

• 从根节点开始，背包初始为空，容量为10，目标是尽量使装入的物品总价值最大化。（PS：此时的物品已经按照单位重量价值进行排序）

• 当什么物品都不装时，重量w为0，上界为背包还剩的重量乘以最大物品的平均重量即：$10\ast 9/7$ . 其次考虑物品 $x_1$（单位重量价值为 $9/7$）。我们有两个选择：装入1个或不装入。装入1个时，重量增加至7，价值变为9；剩余容量仅为3。此时，我们使用代价函数估计：剩余容量3可以继续装入下一种物品 $x_2$，其单位重量价值为 $5/4$。因此，上界为 $9+3\times (5/4)=12.75$，继续探索这条路径。

• 在选择 $x_1=1$ 的路径上，我们进入下一层决策，考虑物品 $x_2$。其最多可以装入10/4=2个，则其可以选择2个、1个和0个的方案。若选择装入2个，则背包重量变为15，不符合约束，减枝；若选择装入1个，重量变为11、减枝；若选择装入0个 $x_2$，背包重量保持为7，价值为9，剩余容量3。计算代价函数为 $9+3\times (3/3)=12$，这符合约束，可以继续探索。此时，我们继续估算下一个物品 $x_3$ 能否装入。（现在你会发现问题的上界变得越来越小，离真实可行解的代价函数值越来越接近）

• 在 $x_1=1$ 且 $x_2=0$ 的路径上，我们接着考虑 $x_3$。如果按照最大重量10来考虑3号物品，其可以装入3个2个1个以及不装。当装入3个2个3号物品时，已经超重。因此，若装入1个$x_3$，总重量达到10，剩下的重量为0，价值为12.更新上界为 $9+3+0\times 1=12$。

• 此时考虑 $x_4$ , 根据总重量4号物品有4、3、2、1、0这五种选择，但是在遍历4号物品选择时，装4个、3个、2个或者1个都会导致重量超重而减枝。因此只能选择装0个四号物品。则此时得到一个可行解。[1,0,1,0]价值为12.则此为一个新的界-12。

• 由于采用深度优先搜索，返回3号物品结点，可以取0值，即不拿3号物品。则计算得到的代价函数值是 $9+3\times 1/2$ (即9是1号的重量，2号不选，剩余3个重量单位，能够选的最大单位重量是4号，如果剩下全拿4号物品，则可能达到的最大重量为 $3\times 1/2=1.5$。则总重量为9+1.5=10.5)。而10.5小于现在的界12.因此对这个节点进行减枝。

• 根据深度遍历的定义，接下来返回到2号物品结点，其子树深度遍历完毕，则返回到1号节点，其子树深度遍历完毕。因此开始搜索不拿一号物品，即$ x_1=0 $ 时的子树。

• 在 $x_1=0$ 时，其代价函数为 $0+10\times 5/4=12.5$（1号物品不拿，则还有10个重量单位剩余，假设全部拿单位重量价值最大的2号物品则价值预期为12.5，这大于当前的界），因此继续向下搜索。

• 在 $x_1=2$ 时，其代价函数为 $10+2\times 3/3=12$ 其不会比当前的界更好-减枝，而如果$x_1=1$ ，其代价函数为 $5+6\times 3/3=11$ 其代价函数更小-减枝， 而如果$x_1=0$ ，其代价函数为 $0+10\times 3/3=10$ 其代价函数更小-减枝。 搜索完毕