Johnson法则证明 | 您所在的位置:网站首页 › edd调度算法证明 › Johnson法则证明 |
Johnson法则证明
在这里先不务正业两句,当我和同机房的某位神犇努力钻研证明过程的时候,非常 气愤为什么编书者如此不负责任的只摆几个看不懂的式子,但是当我们抠懂了之后 书上写的真好 不务正业到此结束 现在开始算法证明:首先如果不知道什么是Johnson法则的可以看《提高篇》第13页, 那里同时也有一篇较为不易理解的证明(也是我写这篇文章的目的) 关于它的题 生产加工调度(一道贪心,一定要看,我后面就是拿它讲的) 首先说一个东西叫做“交换论证”“交换论证”是什么东西呢: 交换论证主要的思想也就是先假设存在一个最优的算法和我们的贪心算法最接近, 然后通过交换两个算法里的一个步骤(或元素),得到一个新的最优的算法,同时 这个算法比前一个最优算法更接近于我们的贪心算法,从而得到矛盾,原命题成立。 以上源自“博客园的一位大佬 文章链接” 以下为我举的一个例子假设现在要做a和b两件事,先做a,再做b 的时间为 T(a,b),那么如果反过来就是 T(b,a)。
我为使 T(a,b) < T(b,a) 得到限定条件(算法),然后按照这个限定条件运行程序,OK。
上面的看不懂也没关系
Johnson法则的证明就运用的交换论证:
S={任务们;}其实S就是个结构体,a是A机器做任务时间,b是B机器的;
现在的最优调度。若在这个调度中,安排在最前面的两个作业分别是i和j。
然后就要上图了
现在开始第一步(列式子):
当然这道题就迎刃而解了 #include #include #include #include using namespace std; int n,ans; struct Node{ int a,b,c; }x[1500]; bool cmp(Node x,Node y){ return min(y.b,x.a) |
CopyRight 2018-2019 实验室设备网 版权所有 |