Get best of the week

《完美算法》一书。贪婪算法和动态规划»

图片您好，habrozhiteli！在新书中，Tim Rafgarden讨论了贪婪算法（规划问题，最小生成树，聚类，霍夫曼代码）和动态编程（背包问题，序列比对，最短路径，最佳搜索树）。这篇文章摘录了“开发贪婪算法”，

贪婪算法似乎非常适合计划工作的任务，从而最大程度地减少了完成时间的加权总和。输出具有迭代结构，其中一次处理一个工作。为什么不使用贪婪算法来迭代确定下一个工作？

我们计划的第一步是解决一般问题的两种特殊情况。我们针对这些情况的解决方案将显示一般情况下贪婪算法的外观。然后，我们将域缩小为一个候选算法，并证明正是该候选者才能正确解决问题。我们记忆该算法的过程比记忆本身更重要。此过程是可重复的，您可以在自己的应用程序中使用它。

13.3.1。两种特殊情况


让我们假设，对于最小化完成日期的加权总和的任务，实际上，有一个正确的贪婪算法。如果我们假设所有作品的长度相同（但权重可能不同），或者相反，权重相同（但长度可能不同），会是什么样呢？
练习13.2

（1）如果所有工作时间都相同，我们是否应该为体重减轻或增加的工作提前计划？
（2）如果所有工作权重都相同，我们应该早些计划更长或更短的工作吗？
a）更多；短
b）较小；短
c）中放大; 长
d）少; long
（有关解决方案和解释，请参阅第13.3.3节。）

13.3.2。决斗贪婪


通常，作品可能具有不同的权重和不同的长度。只要我们有两条经验法则（宁愿较短的工作和较高的权重的工作）有幸能同时完成几项工作，我们就会知道哪个计划最先（较高的权重较短）。但是，如果这两个规则给出了相互矛盾的建议怎么办？一件重量轻的短期作业和一件重量大的长期作业该怎么办？

可以正常工作的最简单的贪婪算法是什么？每个工作都有两个参数，算法应同时考虑两个参数。最好的选择是制定一个公式，将每件作品的长度和重量汇总为一个标记（贡献），这样可以保证从最高标记到最低标记的规划工作将加权完成日期的数量减至最少。如果存在这样的公式，那么从我们的两种特殊情况来看，它必须具有两个属性：（i）保持固定的长度，它应该随着工作的重量而增加； （ii）保持重量不变，应从作品的长度开始减少（记得标记越高越好）。花一分钟的时间集思广益地讨论具有这两个属性的几个公式。

图片

它们之间的区别也许是最简单的功能，其重量增加而长度减小，它们之间的区别是：
作品标记的第1号提案。图片

标出的标记可以是负数，但这不会对从最高到最低标记的作品的连贯构造构成任何障碍。 。但是，还有许多其他选择。例如，两个参数的比率是另一个候选：

用于标记作品的第2号提案，图片

这两个用于计算标记的函数导致两种不同的贪婪算法。
GREEDY DIFFERENCE GREEDYDIFF

按降序计划工作图片
（任意破坏值的重合）。
GREEDYRATIO

图片
( ).

因此，我们的第一个案例研究已经说明了贪婪范式的第一个主题（第13.1.2节）：针对该任务提出几种竞争性贪婪算法通常并不困难。但是，两种算法中的哪一种（如果有）是正确的？排除其中一个的快速方法是找到一个实例，其中两个算法显示具有不同目标函数值的不同时间表。对于本示例中结果较差的任何算法，我们可以得出结论，它并不总是最优的。在两个具有相同重量或相同长度的特殊情况下，两种算法均能正确执行。排除其中一个最简单的例子可能是某项任务的实例，其中两件作品的权重和长度不同，结果，两种算法都计划以相反的顺序工作。也就是说，我们正在寻找两个作品，它们的顺序不同是相对于它们的顺序相反。例：

图片

第一件作品的比例较大，图片但差异较大（–2与–1）。因此，算法首先GreedyDiff计划第二项工作，而算法GreedyRatio则相反。
练习13.3

分别由GreedyDiff和演算法推导出的时间表中加权完成日期的总和是GreedyRatio多少？

a）22和23
b）23和22
c）17和17
d）17和11
（有关解决方案和说明，请参阅第13.3.3节。）

通过将算法排除在GreedyDiff进一步考虑之外，我们向前迈进了一步。但是，练习13.3的结果并不能直接导致该算法GreedyRatio始终是最优的。据我们所知，在其他情况下该算法会产生非最佳计划。您应该始终对没有随附正确性证明的算法持怀疑态度，即使该算法在多个测试案例中做得正确，并且对贪婪算法也极为怀疑。

在我们的案例中，GreedyRatio实际上可以保证算法将加权完成日期的数量减到最少。

定理13.1（算法的正确性GreedyRatio）。对于每组正工作权重图片如果作业长度为正数，则该图片算法GreedyRatio会显示一个计划，该计划的加权完成日期的总和可能最小。

这种逻辑上的陈述并不明显，在没有收到证据的情况下您不应该信任他。根据贪婪范式的第三个主题（第13.1.2节），该证明占据了下一部分的整个内容。
, . .

. — , ( ). — , , , . «» ( ) , .

贪婪范例的其余主题是运行时分析的简便性（第13.1.2节）。当然是这里。GreedyRatio算法仅按关系对作业进行排序，这需要O（n log n）时间，其中n是输入中的作业数（请参阅第24页脚注1）。

13.3.3。练习题13.2–13.3


练习13.2的解决方案

正确答案是：（a）。首先，假设所有n个工作都具有相同的长度（例如1）。然后每个时间表都具有完全相同的最后期限集-{1,2,3，...，n}-唯一的问题是得到什么样的工作完成日期和截止日期是什么？我们关于工作权重的语义当然意味着工作量更大的工作应获得更短的完成时间，这是事实。例如，您不想计划权重为10分之三（期限为3）的工作，而权重为20分之五（期限为5）的工作；您最好改变这两个作品的位置，这样可以将加权截止日期的总和减少20（如您所见）。

第二种情况是，所有作品的重量都相同，但略薄一些。在这里，您希望优先选择较短的工作。例如，考虑两个单位重量为1和2的作业。如果您首先计划一个较短的工作，那么完成期限将是1和3，总数为4。反之，期限是2和3，结果最差5。通常，计划的由于所有工作都必须等待第一项工作的完成，因此第一项工作对所有工作的完成时间都有贡献。在所有条件都相同的情况下，首先计划最短的工作可以最大程度地减少这种负面影响。练习13.3的解决方案第二工作对除第一工作之外的所有完成日期都有贡献，因此，第二最短的工作应在下一个计划中，依此类推。



正确答案是：（b）。该算法首先GreedyDiff计划第二项工作。完成这项工作图片的截止日期是，而完成另一项工作的截止日期是图片加权的完成截止时间之和

图片

该算法GreedyRatio首先计划第一个工作，从而导致最后期限图片
和加权的最后期限之和等于

图片

由于该算法GreedyDiff无法为该示例计算最佳计划，因此它并不总是正确的。

»有关这本书的更多信息，请访问出版商的网站
» 目录
» Khabrozhiteley的节录

优惠券可享受25％的折扣- 算法

支付纸质版本的费用后，就会通过电子邮件发送电子图书。

More articles:


All Articles