我正在尝试理解贪心算法调度问题的工作原理。
因此,我已经阅读和谷歌了一段时间,因为我无法理解贪心算法调度问题。
我们有n个工作要在单个资源上安排。任务(i)具有请求的开始时间s(i)和完成时间f(i)。
有一些贪心的想法可以选择...
- 按照s的递增顺序接受(“最早开始时间”) - 按照f - s的递增顺序接受(“最短任务时间”) - 按照冲突数量的递增顺序接受(“最少冲突”) - 按照f的递增顺序接受(“最早完成时间”)
书中说最后一个,按照f的递增顺序接受总是会给出最优解。
然而,它没有提到为什么它总是提供最优解,以及为什么其他三个不会提供最优解。
他们提供了这张图,说明为什么其他三个不能提供最优解,但我不明白它是什么意思。
由于我的声誉不高,我无法发布任何图像,所以我将尝试绘制它。 |---| |---| |---| |-------------------------| 按照s的递增顺序接受 低估的解决方案 |-----------| |-----------| |-----| 按照f - s的递增顺序接受 低估的解决方案 |----| |----| |----| |----|
|-----| |-----| |-----|
|-----| |-----|
|-----| |-----|
按冲突数量的递增顺序接受。 低估的解决方案
这就是它的样子,我不明白这是每种情况的反例。
如果有人能解释为什么每个贪心想法是否有效,那将非常有帮助。
谢谢。
因此,我已经阅读和谷歌了一段时间,因为我无法理解贪心算法调度问题。
我们有n个工作要在单个资源上安排。任务(i)具有请求的开始时间s(i)和完成时间f(i)。
有一些贪心的想法可以选择...
- 按照s的递增顺序接受(“最早开始时间”) - 按照f - s的递增顺序接受(“最短任务时间”) - 按照冲突数量的递增顺序接受(“最少冲突”) - 按照f的递增顺序接受(“最早完成时间”)
书中说最后一个,按照f的递增顺序接受总是会给出最优解。
然而,它没有提到为什么它总是提供最优解,以及为什么其他三个不会提供最优解。
他们提供了这张图,说明为什么其他三个不能提供最优解,但我不明白它是什么意思。
由于我的声誉不高,我无法发布任何图像,所以我将尝试绘制它。 |---| |---| |---| |-------------------------| 按照s的递增顺序接受 低估的解决方案 |-----------| |-----------| |-----| 按照f - s的递增顺序接受 低估的解决方案 |----| |----| |----| |----|
|-----| |-----| |-----|
|-----| |-----|
|-----| |-----|
按冲突数量的递增顺序接受。 低估的解决方案
这就是它的样子,我不明白这是每种情况的反例。
如果有人能解释为什么每个贪心想法是否有效,那将非常有帮助。
谢谢。