背包问题-分支限界法求解
背包问题-分支限界法求解
背包问题是一个经典的组合优化问题，其目标是在满足重量约束的前提下，最大化所选物品的总价值。分支限界法是一种有效的求解方法，通过构建决策树并利用代价函数进行剪枝，可以高效地找到最优解。本文将详细介绍分支限界法的基本概念、背包问题的实例分析以及具体的求解过程。
1. 分支限界法的基本概念与背包问题实例
1.1 组合优化问题的基础概念
组合优化问题涉及在有限的解空间内，找到满足某种约束条件的最优解。这些问题通常出现在资源分配、路径规划和背包问题等场景中。
目标函数：用于描述我们希望最大化或最小化的属性（如最大化背包的价值、最小化路径长度等）。
最大化问题示例：最大化装入背包的物品总价值。
最小化问题示例：寻找最短路径覆盖所有城市。
约束条件：限定了可行解的条件。例如，背包问题中，物品总重量不能超过背包容量。
可行解：在所有解中，满足约束条件的解称为可行解。
示例：对于一个背包问题，总重量小于等于背包容量的物品组合就是可行解。
最优解：在可行解中，使目标函数达到最大值（最大化问题）或最小值（最小化问题）的解。
示例：在可行解中，选出价值最大的物品组合。
1.2 背包问题示例分析
背包问题是一个典型的组合优化问题，其求解过程涉及如何合理地选择物品，以便在满足约束条件的前提下，使物品的总价值达到最大。
示例
目标函数：
$$
\max \quad 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 \leq 10
$$
每个物品的重量受限于背包的最大容量10。解的表示：
$x_i = 1$：选择物品i；
$x_i = 0$：不选择物品i。
示例求解过程：
- 选择物品1：总重量为 2，价值为 1。
- 选择物品2和3：总重量为3 + 4 = 7，价值为3 + 5 = 8。
- 验证可行性：若当前选择使得重量小于等于10，则该组合为可行解。
1.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 \quad x_1 + 3x_2 + 5x_3 + 9x_4
$$
约束条件：
$$
2x_1 + 3x_2 + 4x_3 + 7x_4 \leq 10, \quad x_i \in \mathbb{N}, \quad i = 1, 2, 3, 4
$$
1.5.2 代价函数的设定
- 代价函数用于估计在剩余背包容量内可以达到的最大价值，并指导搜索树的剪枝。对结点$<x_1, x_2, ..., x_k>$, 估计以该结点为根的子树中可行解的上界。
- 单位重量价值的排序：计算每个物品的单位重量价值$v_i / w_i$：
- $9/7, \quad 5/4, \quad 3/3, \quad 1/2$
- 排序后：4号物品 > 3号物品 > 2号物品 > 1号物品。即排在前面的物品单位价值更高，而排在后面的物品，单位价值更低
- 代价函数公式：$\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$。
**$v_{k+1} / w_{k+1}$：**表示单位重量价值最高的物品。按物品的单位重量价值从高到低排序，确保优先装入高价值的物品，最大化潜在收益。
特殊情况：
如果剩余空间足够大，则继续装入单位重量价值最高的物品，计算出$\Delta$的上界。
如果没有物品能够再装入背包，则$\Delta = 0$，即无法进一步增加价值。
对于某个节点$\langle x_1, x_2, \dots, x_k \rangle$，即前$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}$。
代价函数的计算逻辑
排序物品：将所有物品按单位重量价值$v_i / w_i$从大到小排序。排序后的物品优先尝试装入，以保证在剩余空间内最大化背包的价值。
剩余空间的估计：假设背包剩余的空间为$b - \sum_{i=1}^{k} w_i \cdot x_i$。如果剩余空间足够大，可以装入单位重量价值最高的物品。
剩余价值的估计：
- 如果剩余空间允许，将其完全用单位价值最高的物品填充。即乘以$v_{k+1} / w_{k+1}$，得到剩余空间的价值上界。
- 若剩余空间不够放入任何物品，则第二项为 0。
1.5.3 背包问题的分支限界法实例推导过程
1.5.3.1 决策树的推导过程分析
本次推导采用深度优先搜索（DFS）与代价函数相结合的方式，在搜索树中动态计算每个节点的价值上界，确保高效剪枝。我们从根节点开始依次装入物品，逐步计算背包的剩余容量和价值，根据状态判断是否继续探索或进行剪枝。
在背包问题中，每层的节点代表对某个物品的选择，即装入一定数量的该物品或不装入。随着搜索的进行，剩余容量逐渐减少，代价函数为每条路径提供一个潜在的价值上界，当上界不如当前的最佳解时，立即剪枝。
1.5.3.2 推导过程详细分析
从根节点开始，背包初始为空，容量为10，目标是尽量使装入的物品总价值最大化。（PS：此时的物品已经按照单位重量价值进行排序）
当什么物品都不装时，重量w为0，上界为背包还剩的重量乘以最大物品的平均重量即：$10*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\times1=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\times1/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$其代价函数更小-减枝。
搜索完毕