理解调度以最小化迟到问题
Understanding scheduling to minimize lateness problem
我正在阅读以下内容 link 以更好地了解算法的最优性。我想知道为什么需要 "inversion" 来证明最优性？一段时间以来，我一直在摸不着头脑。任何帮助表示赞赏。谢谢！
https://kartikkukreja.wordpress.com/2013/11/24/scheduling-to-minimize-lateness/
逻辑是：
假设有一个最优解：
1) 与引入 NO EXTRA latency 的最佳解决方案相比，始终存在无反转版本的解决方案；
2) 如果 1) 是可靠的，那么我们可以将问题缩小到如何安排作业以最小化空闲时间
3) 显然，所提出的解决方案已经最小化了空闲时间，因为空闲时间为 0。
所以，简而言之，引入倒置就是缩小问题范围，尽量减少空闲时间。
我正在阅读以下内容 link 以更好地了解算法的最优性。我想知道为什么需要 "inversion" 来证明最优性？一段时间以来，我一直在摸不着头脑。任何帮助表示赞赏。谢谢！
https://kartikkukreja.wordpress.com/2013/11/24/scheduling-to-minimize-lateness/
逻辑是：
假设有一个最优解： 1) 与引入 NO EXTRA latency 的最佳解决方案相比，始终存在无反转版本的解决方案；
2) 如果 1) 是可靠的，那么我们可以将问题缩小到如何安排作业以最小化空闲时间
3) 显然，所提出的解决方案已经最小化了空闲时间，因为空闲时间为 0。
所以，简而言之，引入倒置就是缩小问题范围，尽量减少空闲时间。