貪婪算法，調度

Question

我想了解貪婪算法調度問題是如何工作的。

所以我一直在閱讀和谷歌搜索一段時間，因爲我無法理解貪婪算法調度問題。

我們有n個工作安排在單個資源上。工作（i）具有請求的開始時間s（i）和結束時間f（i）。

有我們選擇一些貪婪的想法...

• 接受增加S的順序（「最早開始時間」）
• 接受增加的F順序 - S（「最短工作時間「）
• 接受增加的衝突（數的順序」衝突最少「）
• 接受在增加F（順序」最早結束時間「）

而書上說的最後一個，接受順序遞增的f總會給出一個最優解。

但是沒有提到它總是給出最優解的原因，以及爲什麼其他3不會給出最優解。

他們提供的數字說明了爲什麼其他三個不會提供最佳解決方案，但我不明白它的含義。

由於我的聲望很低，我無法發佈任何圖片，所以我會嘗試繪製它。

| --- | | --- | | --- |
| ------------------------- |
s的遞增順序 低估的解決方案

| ----------- | | ----------- |
| ----- |
f-s的遞增順序 低估的解決方案

| ---- | | ---- | | ---- | | ---- |

| ----- | | ----- | | ----- |

| ----- | | ----- |

| ----- | | ----- |

增加衝突次數的順序。 低估解決方案

這是它的樣子，我不明白爲什麼這是每個場景的反例。

如果任何人都可以解釋爲什麼每個貪婪的想法都行不通，那將會非常有幫助。

謝謝。

Answer 1

由於@ vish4071已經解釋了爲什麼選擇最早的完成時間將導致最佳解決方案，我只會解釋反例。任務[a,b]開始於a並結束於b。我將使用您提供的反例。

1. 最早開始時間

假設任務[1,10]，[2,3]，[4,5]，[6,7]。最早的開始時間策略將選擇[1,10]，然後拒絕其他3個，因爲它們都與第一個碰撞。但我們可以看到，[2,3], [4,5], [6,7]是最佳解決方案，因此最早的開始時間策略並不總能產生最佳結果。

最短執行時間

假設任務[1,10]，[11,20]，[9,12]。此策略將選擇[9,12]，然後拒絕另外兩個，但最佳解決方案是[1,10]，[11,20]。因此，最短的執行時間策略並不總是會導致最佳結果。

最不衝突

這一戰略似乎有希望的，但有11個任務，你的例子證明了這一點不會是最佳的量。假設任務：[1,4],3x [3,6],[5,8], [7,10], [9,12],3x和[13, 16]。 [7,10]與其他任務只有2次衝突，這比其他任務要少，所以首先通過最少量的衝突策略來選擇它。然後選擇[1,4]和[13, 16]，並且所有其他任務因爲與已選任務相沖突而被拒絕。這是3個任務，但是可以選擇4個任務而不發生衝突：[1,4],[5,8],[9,12]和[13, 16]。

您還可以看到，在這些示例中，最早完成時間策略將始終選擇最佳解決方案。請注意，使用相同數量的選定任務可以存在多個最佳解決方案。在這種情況下，最早的完成時間策略將總是選擇其中的一個。

Answer 2

我想我可以解釋這一點。
比方說，我們有n個工作，開始時間爲s[1..n]，結束時間爲f[1..n]。因此，如果我們按照完成時間對其進行排序，那麼我們將始終能夠完成大部分任務。讓我們看看，如何。

如果一個工作更早完成（即使它在系列後面開始，一個短期工作），那麼，我們總是有更多的時間用於以後的工作。我們假設，我們還有其他工作可以在這段時間內開始/完成，以便我們的任務數量可以增加。現在，這是不可能的，因爲如果在此之前完成了任何任務，那麼這將是最早完成時間的任務，因此我們將在那一個上完成任務。而且，如果任何任務到目前爲止尚未完成（但已經開始），那麼如果我們選擇了這個任務，我們就不會完成任何任務，但現在我們至少已經完成了任務。所以，無論如何，這是最佳選擇。
有很多可能的解決方案，可以在一個區間內完成最多數量的任務，EFT提供了一個這樣的解決方案。但它總是可能的最大數量。

我希望我能解釋得很好。