如果在单处理器上,有 n 个运行时间分别为𝑡1,𝑡2, ⋯ ,𝑡𝑛的已知作业,请考虑 安排一个调度计划,使得所有作业花费在系统中的时间最少(一个作业花费 在系统中的时间是该作业用于等待的时间和用于运行的时间之和)。为该问题 设计一个贪婪算法,写出伪代码,讨论所设计的贪婪算法是否总能产生最优解。
时间: 2024-01-24 10:18:34 浏览: 45
贪心算法:
将所有作业按照运行时间从小到大排序,然后从前往后依次分配给处理器,使得处理器的总运行时间最小。
伪代码:
1. 对所有作业按照运行时间从小到大排序
2. 初始化 n 个处理器的运行时间为 0
3. 依次将每个作业分配给当前总运行时间最小的处理器
4. 更新处理器的运行时间
5. 输出处理器的总运行时间
该贪心算法能够产生最优解。证明如下:
假设该算法得到的调度方案不是最优的,存在一种调度方案比该算法得到的更优。考虑两种方案下安排最后一个作业的处理器。
在该算法得到的方案中,最后一个作业被分配给了当前总运行时间最小的处理器。
在比该算法更优的方案中,最后一个作业被分配给了其他处理器。因为该算法在处理前面的作业时已经考虑了当前总运行时间最小的处理器,所以其他处理器的总运行时间一定大于等于当前总运行时间最小的处理器。因此,将最后一个作业分配给其他处理器不会使得处理器的总运行时间更小,与假设矛盾。
因此,该贪心算法是正确的。
相关问题
如果在单处理器上,有 n 个运行时间分别为𝑡1,𝑡2, ⋯ ,𝑡𝑛的已知作业,请考虑 安排一个调度计划,使得所有作业花费在系统中的时间最少(一个作业花费 在系统中的时间是该作业用于等待的时间和用于运行的时间之和)。为该问题 设计一个贪婪算法,讨论所设计的贪婪算法是否总能产生最优解。
可以采用贪心算法解决这个问题,具体步骤如下:
1. 将所有作业按照运行时间从小到大排序。
2. 依次将每个作业分配给当前负载最小的处理器,即当前总运行时间最少的处理器。
3. 重复步骤2直到所有作业都被分配完毕。
这个算法被称为最短作业优先(SJF)算法。它的贪心策略是优先选择运行时间最短的作业,并尽可能让它们先完成。
这个贪心算法能够产生最优解,也就是最小化所有作业花费在系统中的时间。证明如下:
假设存在一个最优解,它将作业分配给了某些处理器,使得总运行时间比我们的贪心算法更小。但是,我们可以将这些处理器中运行时间最小的作业移动到我们的贪心算法所选择的处理器中,这样总运行时间会更小。这与我们的贪心算法冲突,因为它已经选择了运行时间最短的作业。因此,我们的贪心算法是最优的。
需要注意的是,这个贪心算法假设所有作业的运行时间是已知的。如果作业的运行时间不确定,我们可以采用另一种贪心算法,称为最短剩余时间优先(SRTF)算法。在SRTF算法中,我们每次选择剩余运行时间最短的作业运行,这样能够更准确地估计作业的花费时间。
如果在单处理器上,有 n 个运行时间分别为 t1,t2,t3, …, tn的已知作业,请考 虑它们的调度问题。这些作业可以按任意顺序执行,一次只能执行一个作业。 要求: (1)安排一个调度计划,使得所有的作业在系统中花费的时间最少 (一个作业在系统中花费的时间是该作业用于等待的时间和用于运行的时间的总和。) 思路:按照作业运行时间递增的顺序进行调度(运行时间一样,按照id递增的顺序进行调度 为该问题设计一个贪婪算法; (2)分析该贪婪算法是否总是能产生最优解?
贪婪算法的设计思路如下:
1. 将所有作业按照运行时间递增的顺序排序,如果有运行时间相同的作业,则按照 ID 递增的顺序排列。
2. 从排序后的作业列表中取出第一个作业,将其放入系统中运行。
3. 对于后面的每个作业,计算其在系统中等待的时间。等待时间 = 前面所有作业的运行时间之和。
4. 选择等待时间最短的作业,将其放入系统中运行。
5. 重复步骤 3 和步骤 4,直到所有作业都被放入系统中运行。
该贪婪算法可以得到一个近似最优解,但不一定总是最优解。因为该算法只考虑了当前作业在等待时间上的贡献,而没有考虑后续作业的影响。例如,在某些情况下,等待时间短的作业可能会占用资源,导致后续作业的等待时间变长,从而降低整体的效率。因此,该贪婪算法不能保证总是能产生最优解。