许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/组合优化问题涉及在有限的解空间内，找到满足某种约束条件的最优解。
这些问题通常出现在资源分配、路径规划和背包问题等场景中。
目标函数：用于描述我们希望最大化或最小化的属性（如最大化背包的价值、最小化路径长度等）。
约束条件：限定了可行解的条件。例如，背包问题中，物品总重量不能超过背包容量。
可行解：在所有解中，满足约束条件的解称为可行解。
最优解：在可行解中，使目标函数达到最大值（最大化问题）或最小值（最小化问题）的解。
背包问题是一个典型的组合优化问题，其求解过程涉及如何合理地选择物品，以便在满足约束条件的前提下，使物品的总价值达到最大。
目标函数：
\[\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。
解的表示：
代价函数是一个估计函数，用于衡量当前节点及其子树中的解的上界（或下界）。
代价函数有助于在搜索过程中剪枝，即提前判断某些分支是否值得继续探索。
代价函数的计算位置：
每当搜索到一个节点时，都会计算该节点的代价函数值。
代价函数的意义：
界的定义：
界是当前已找到的最优解的目标函数值。对于极大化问题，界是最大值；对于极小化问题，界是最小值。
界的作用：
在搜索过程中，界用于判断是否继续探索某条分支。如果当前节点的代价函数值低于界，则该节点无需继续搜索，因为它无法提供更好的解。
目标：
选择装入背包的物品，使得总重量不超过 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 \]
单位重量价值的排序：
计算每个物品的单位重量价值 \(v_i / w_i\)：
代价函数公式：
\(\Delta\) 是代价函数的关键部分，用于估计背包中剩余容量的最大利用潜力。
\[F(x) = \text{已装入价值} + \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}}\)：
表示单位重量价值最高的物品。按物品的单位重量价值从高到低排序，确保优先装入高价值的物品，最大化潜在收益。
特殊情况：
对于某个节点 \(\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\)。如果剩余空间足够大，可以装入单位重量价值最高的物品。
剩余价值的估计：
本次推导采用深度优先搜索（DFS）与代价函数相结合的方式，在搜索树中动态计算每个节点的价值上界，确保高效剪枝。我们从根节点开始依次装入物品，逐步计算背包的剩余容量和价值，根据状态判断是否继续探索或进行剪枝。
在背包问题中，每层的节点代表对某个物品的选择，即装入一定数量的该物品或不装入。随着搜索的进行，剩余容量逐渐减少，代价函数为每条路径提供一个潜在的价值上界，当上界不如当前的最佳解时，立即剪枝。
从根节点开始，背包初始为空，容量为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\times1/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\times3/3=11\) 其代价函数更小-减枝， 而如果\(x_1=0\) ，其代价函数为 \(0+ 10\times3/3=10\) 其代价函数更小-减枝。 搜索完毕
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。