江苏龙网

  1. 首页 > 生活 > >

求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗

【求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗】 你的链接里面说是NP完全的，那大概就是吧……
如果只是尽量优化的话：
考虑相邻的两个任务，它们从s1开始，到f2结束，需要的时间分别是t1,t2，则f1=s2=s1+t1, f2=s2+t2。如果交换它们，则仍然从f1\u0026#39;=s2\u0026#39;=s1+t2, s2保持不变。其他任务的开始和结束均保持不变。
总的延迟的差为
求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗

注意到
求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗

所以原式
求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗

求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗

如果该表达式\u0026gt;0，则可以交换相邻两个达到更优的结果。
注意在 求最佳调度顺序，使得总共延期时间最少。 可以在多项式时间解决吗，或贪心可以解决吗
时，该表达式恒\u0026lt;=0，这个结果还可以推广到不相邻的情况，也就是说如果两个任务A和B，A比B早截止，且A比B耗时短，则A一定比B先安排。

既然没有多项式的方法，那剩下的就随便了，可以先贪心一次然后用贪心的结果做搜索剪枝，比如说可以：
先算出所有时间总和，然后从后往前安排如果有截止时间在当前时间之后的，立即安排；否则安排耗时最长的按前面的公式检查能否交换相邻两个得到更优的结果随便搜一下，用前面的结果做剪枝，注意到可以通过估算剩下的任务的延迟总和下限来剪枝
■网友
既然说了是NPH那就是吧


    推荐阅读


    上一篇：Java怎样利用Math.random()产生泊松分布随机数

    下一篇：到底是高频交易更需要数学能力还是中低频交易更需要