贪婪解对作业排序的最优性证明

Question

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

此外，正如作者后来声称的那样，我也无法找出O（n）解决方案

可以通过使用联合查找数据结构将其优化为几乎O（n）。

Answer 1

贪婪解的最优性可以通过以下交换论点看出。在不失一般性的前提下，假设所有利润都是不同的，并且职位按利润的降序排列。

修复解决方案S。从此解决方案中，删除所有错过截止日期的作业。通过此转换，每个工作都在其截止日期之前完成，因此得出的解决方案S1仍然是最佳的。对于作业i，请考虑间隔I_i:=[0,min(n,deadline(i))]（如在贪婪算法中一样）。在此间隔内，在作业i的右边，只有处理时间较长的作业（如果没有，则可能是我们的订单早考虑了这些作业，或者可以在不违反最后期限的情况下进行更换）。将作业i放置在I_i中可能的最右边位置。

总共，我们有以下语句。

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

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

特别是，存在具有上述特性的最优解S*。令S是由贪婪算法生成的算法。注意，S也具有上面的属性2和3。令i是在S中发生的第一工作，但不在S*中发生。令pos为i中S的时隙。如果pos中的S*为空，则可以通过添加S*来改进i，这与S*的最佳性相反。如果pos中的S*为空，则i'中pos中的S*职位的利润不能大于i，因为否则贪婪算法会选择i'在pos中的S处。因此，它的利润必须低于i。这意味着可以将其删除并替换为i中的S*，这也与S*的最佳性相矛盾。

Answer 2

1. 正确性证明。让我们假设这是不正确的。这是什么意思？这意味着在某个步骤中我们已经放弃了一项工作，因为如果不删除已经采取的工作就无法添加它。如果我们删除了一个已经使用的时隙并将其放入其时隙中，则我们不会为下一个作业做任何更改（占用时隙的集合将是相同的）。但是总利润会减少。因此，该算法产生的解是最优的。

Answer 3

考虑一份截止日期为4的工作，价值2分，而截止日期为3的每项工作，价值3分，这是3个工作。 ，之前比较贵。

Answer 4