工作排序贪婪解决方案的最优性证明
Proof of optimality of a greedy solution to job sequencing
在这个Job Sequencing Problem中，我们如何证明贪心算法给出的解是最优解呢？
而且，我也想不出作者后来声称的O(n)解决方案
It can be optimized to almost O(n) by using union-find data structure.
贪心解的最优性可以通过如下交换论证看出。不失一般性，假设所有利润都不同，并且工作按利润递减顺序排列。
修复一个解决方案S。从此解决方案中，删除所有错过截止日期的作业。
由于通过这种转换，每项工作都在其截止日期内完成，因此得到的解决方案 S1 仍然是最优的。对于作业 i，考虑区间 I_i:=[0,min(n,deadline(i))]（如在贪心算法中）。在此区间内，作业 i 的右侧，只有处理时间较长的作业（如果不是，它们要么会被我们的订单提前考虑，要么可以在不违反截止日期的情况下进行交换）。将工作 i 放在 I_i.
中可能的最右边位置
总的来说，我们有以下语句。
每个解决方案 S 都可以转换为具有以下属性的解决方案 S'。
S' 包含 S 中在截止日期前完成的所有作业。- 对于
S 中的每个作业 i，I_i 中 i 之后的所有作业都有较长的处理时间。
- 对于
S中的每个作业i，在I_i中i之后没有空闲时间。
S' 与 S.
特别地，存在具有上述性质的最优解S*。设S为贪心算法生成的算法。请注意 S 也具有上面的属性 2 和 3。设 i 是第一个出现在 S 但不在 S* 的工作。设pos为S中i的时隙。如果 pos 在 S* 中为空，则可以通过添加 i 来改进 S*，这与 S* 的最优性相矛盾。如果 pos 在 S* 中 不是 是空的，S* 中 pos 的工作 i' 不能有更大的利润比 i，否则贪婪算法会选择 i' 在 S 中的 pos。因此，它的利润肯定低于i。这意味着它可以被删除并替换为S*中的i，这也与S*的最优性相矛盾。
考虑一份价值 2 分的工作，截止日期为 4，三份工作每份价值 1 分，截止日期为 3。这 反驳 "greedy" 算法的最优性：先做三个便宜的工作，然后再做更昂贵的工作，这样更有利可图。
至于 O(n^2) 与 O(n)，我认为这两种说法都是错误的。 "greedy" 算法，如前所述，包括对作业进行排序 - O(nlogn) - 加上排序列表的单次扫描，填充解决方案序列槽 - O(n) - 因此是 O(nlogn)。
为了使其线性，必须对排序做一些事情，例如使用基数排序，这在实际应用中可以被认为是线性的。
正确性证明。让我们假设它是不正确的。这是什么意思？这意味着在某个步骤我们已经丢弃了一项工作，因为如果不删除已经采取的工作就不可能添加它。如果我们删除了一个已经占用的作业并将当前作业放入它的时间段，我们就不会为下一个作业更改任何内容（占用的时间槽集将是相同的）。但总利润会减少。因此，该算法产生的解是最优的。
使其比 O(n ^ 2) 更快。为此，我们需要快速找到给定位置左侧最右边的空闲位置。如果我们使用union-find结构来维护一组被占用的位置，我们可以只找到当前工作的截止日期所在的组和它左边的一个take元素。但是因为排序的原因还是O(n log n)。
给出的证明不完整。也就是说，句子 "the job i'at pos in S* cannot be of larger profit than i" 没有被证明，我认为不可能。无论如何，可以证明即使工作i的利润大于或等于i''，该陈述也成立。
在这个Job Sequencing Problem中，我们如何证明贪心算法给出的解是最优解呢？
而且，我也想不出作者后来声称的O(n)解决方案
It can be optimized to almost O(n) by using union-find data structure.
贪心解的最优性可以通过如下交换论证看出。不失一般性，假设所有利润都不同，并且工作按利润递减顺序排列。
修复一个解决方案S。从此解决方案中，删除所有错过截止日期的作业。
由于通过这种转换，每项工作都在其截止日期内完成，因此得到的解决方案 S1 仍然是最优的。对于作业 i，考虑区间 I_i:=[0,min(n,deadline(i))]（如在贪心算法中）。在此区间内，作业 i 的右侧，只有处理时间较长的作业（如果不是，它们要么会被我们的订单提前考虑，要么可以在不违反截止日期的情况下进行交换）。将工作 i 放在 I_i.
总的来说，我们有以下语句。
每个解决方案 S 都可以转换为具有以下属性的解决方案 S'。
S'包含S中在截止日期前完成的所有作业。- 对于
S中的每个作业i，I_i中i之后的所有作业都有较长的处理时间。 - 对于
S中的每个作业i，在I_i中i之后没有空闲时间。 S'与S. 具有相同的 objective 值
特别地，存在具有上述性质的最优解S*。设S为贪心算法生成的算法。请注意 S 也具有上面的属性 2 和 3。设 i 是第一个出现在 S 但不在 S* 的工作。设pos为S中i的时隙。如果 pos 在 S* 中为空，则可以通过添加 i 来改进 S*，这与 S* 的最优性相矛盾。如果 pos 在 S* 中 不是 是空的，S* 中 pos 的工作 i' 不能有更大的利润比 i，否则贪婪算法会选择 i' 在 S 中的 pos。因此，它的利润肯定低于i。这意味着它可以被删除并替换为S*中的i，这也与S*的最优性相矛盾。
考虑一份价值 2 分的工作，截止日期为 4，三份工作每份价值 1 分，截止日期为 3。这 反驳 "greedy" 算法的最优性：先做三个便宜的工作，然后再做更昂贵的工作，这样更有利可图。
至于 O(n^2) 与 O(n)，我认为这两种说法都是错误的。 "greedy" 算法，如前所述，包括对作业进行排序 - O(nlogn) - 加上排序列表的单次扫描，填充解决方案序列槽 - O(n) - 因此是 O(nlogn)。
为了使其线性，必须对排序做一些事情，例如使用基数排序，这在实际应用中可以被认为是线性的。
正确性证明。让我们假设它是不正确的。这是什么意思？这意味着在某个步骤我们已经丢弃了一项工作，因为如果不删除已经采取的工作就不可能添加它。如果我们删除了一个已经占用的作业并将当前作业放入它的时间段，我们就不会为下一个作业更改任何内容（占用的时间槽集将是相同的）。但总利润会减少。因此，该算法产生的解是最优的。
使其比
O(n ^ 2)更快。为此，我们需要快速找到给定位置左侧最右边的空闲位置。如果我们使用union-find结构来维护一组被占用的位置，我们可以只找到当前工作的截止日期所在的组和它左边的一个take元素。但是因为排序的原因还是O(n log n)。
给出的证明不完整。也就是说，句子 "the job i'at pos in S* cannot be of larger profit than i" 没有被证明，我认为不可能。无论如何，可以证明即使工作i的利润大于或等于i''，该陈述也成立。