algorithm - 了解调度以最小化延迟问题

Question

我正在阅读以下链接以更好地了解算法的最优性。我想知道为什么需要“反转”来证明最优性？我一直在为此挠头。任何帮助表示赞赏。谢谢！

https://kartikkukreja.wordpress.com/2013/11/24/scheduling-to-minimize-lateness/

标签： algorithmgreedy

Answer 1

逻辑是：

假设有一个最优解： 1) 与没有引入额外延迟的最优解相比，总是有一个无反转版本的解；

2）如果1）是可靠的，那么我们可以将问题缩小到如何调度作业以最小化空闲时间

3) 显然，所提出的解决方案已经最小化了空闲时间，因为空闲时间为 0。

所以，简而言之，引入倒置是为了缩小问题范围以最小化空闲时间。