algorithm - 工作排序贪婪解决方案的最优性证明

Question

在此Job Sequencing Problem ，我们如何证明贪婪方法提供的解决方案是最优的？

此外，我也无法找出作者后来声称的 O(n) 解决方案

It can be optimized to almost O(n) by using union-find data structure.

Answer 1

贪婪解决方案的最优性可以通过如下交换参数看出。在不失一般性的情况下，假设所有利润都不同，并且工作按利润降序排列。

修复解决方案 S。从此解决方案中，删除所有错过截止日期的作业。由于通过这种转换，每项工作都在其截止日期内完成，因此生成的解决方案 S1 仍然是最优的。对于作业 i，考虑区间 I_i:=[0,min(n,deadline(i))](与贪心算法一样)。在此间隔内，作业 i 的右侧，只有处理时间较长的作业(如果不是，它们要么会被我们的订单提前考虑，要么可以在不违反它们的情况下进行交换截止日期)。将作业 i 放在 I_i 中最右边的位置。

总的来说，我们有以下陈述。

每个解决方案 S 都可以转换为具有以下属性的解决方案 S'。

1. S' 包含 S 的所有在截止日期前完成的作业。
2. 对于S中的每个作业i，I_i中i之后的所有作业都有较长的处理时间。
3. 对于S中的每个作业i，在I_i中的i之后没有空闲时间。<
4. S' 与 S 具有相同的目标值。

特别地，存在具有上述性质的最优解S*。令S为贪心算法生成的算法。请注意，S 还具有上面的属性 2 和 3。设 i 是出现在 S 中但不在 S* 中的第一个作业。令pos为S中i的时隙。如果 S* 中的 pos 为空，则可以通过添加 i 来改进 S*，这与最优性相矛盾S*。如果 pos 在 S* 中不为空，作业i'在pos S* 中的利润不能大于 i，否则贪心算法会选择 i' 位于 pos 在 S 中。因此，它的利润一定低于i。这意味着它可以被S*中的i删除和替换，这也与S*的最优性相矛盾。