在文章《貪婪演算法》中, 我們已經講述了貪婪演算法NP 問題的定義. 今天, 我們要使用貪婪演算法來解決兩個問題 : 機器調度問題和箱櫃裝載問題

例 1. [任務排程] 一個工廠有 m 台機器, 工廠接受了 n 個任務, 第 i 個任務的處理時間為 t_{i}. 其中, i = 1, 2, ..., n. 若一台機器同一時間至多只能處理一個任務, 一個任務不可同時在兩台機器上進行處理. 我們要找到一個方案, 使得 n 個任務在 m 台機器上用時最少的最佳排程方案

例 2. [箱櫃裝載] 設有等待裝載的物品 n 個, 第 i 個物品所佔用的容量為 w_{i}. 其中, i = 1, 2, ..., n. 箱櫃的數量不限, 但是每個箱櫃至多能夠裝載的容量為 c. 我們要找到一個方案, 使得所有物品都可以被裝載並且箱櫃使用的數量最少

這一類問題都是 NP 問題, 而且上面兩個問題都可以化約為 NP-完全問題. 例 1 可以化約為是否存在一個用時最少的方案, 例 2 可以化約為是否存在一個箱櫃使用量最少的方案. 其答案僅限於是或者否

在之前講述 NP 問題的時候, 我們已經說過, 我們雖然可能無法找到一個最佳的解決方案, 但是我們可以憑藉著我們的生活經驗, 制定貪婪準則, 得到一個近似演算法. 這個近似演算法的性能和最佳化的演算法性能相接近

那麼在任務排程的問題中, 我們可以使用的生活經驗有 :

  1. 按順序排程, 先來先處理
  2. 按任務重要程度進行排程
  3. 按任務處理需要的時長進行排程 (從小到大或者從大到小)
  4. 隨機排程
  5. ...

在箱櫃裝載問題中, 我們可以使用的生活經驗有 :

  1. 最先適配 : 按順序裝載, 每次裝載時選擇前面可以裝載物品的箱櫃
  2. 最佳適配 : 裝載時選擇可以容納物品但是剩餘容量最小的箱櫃
  3. 最先適配遞減 : 執行最先適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序
  4. 最佳適配遞減 : 執行最佳適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序
  5. 最後適配 : 按順序進行裝載, 每次裝載時選擇最後面可以裝載物品的箱櫃
  6. 最差適配 : 按順序進行裝載, 每次裝載時選擇可以容納物品但是剩餘容量最大的箱櫃
  7. 最後適配遞減 : 執行最後適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序
  8. 最差適配遞減 : 執行最差適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序
  9. 隨機適配 : 隨機選取箱櫃, 當箱櫃可以容納物品的時候就裝載; 否則, 重新選區箱櫃
  10. 相鄰適配 : 為了裝載一件物品, 首先在非空的箱櫃中循環搜尋能夠裝載該物品的箱櫃. 如果找不到這樣的箱櫃, 那麼就啟用一個新的箱櫃. 開始時, 沒有非空的箱櫃, 那麼就啟用箱櫃 1 裝載物品 1. 不妨設箱櫃 1 至箱櫃 b 已經裝載了物品, 其中 b \geq 1. 我們將所有箱櫃從箱櫃 1 開始直到箱櫃 b 排列為一個環. 設第 i 個箱櫃是上一次被裝載的箱櫃 : 當 i \neq b 的時候, i 的下一個箱櫃為 i + 1; 當 i = b 時, i 的下一個箱櫃為箱櫃 1 (i = 1, 2, ..., b). 下一次再搜尋的時候, 從第 i 個箱櫃開始搜尋, 直到找到一個合適的箱櫃或者啟用一個空箱櫃為止
  11. ...

對於任務排程的問題, 我們需要憑藉實際問題中的限制來選取貪婪策略, 但是對於箱櫃裝載的問題, 必定存在一個最佳的策略. 我們之前說過, 要想證明某一個貪婪演算法可以產生最佳解, 那麼就需要使用數學證明

斷言 : 在箱櫃裝載問題中, 將方案 4 作為貪婪準則, 使用貪婪演算法產生的結果是最佳解

證明 :

不失一般性. 設所有的物品被裝載之前已經按照重量從小到大排序, 即 \mathscr {W} = \left \{ w_{1}, w_{2}, ..., w_{n} \right \}, w_{i} \leq w_{i + 1} (i = 1, 2, ..., n - 1). 設 \mathscr {X} = \left \{ x_{1}, x_{2}, ..., x_{n} \right \} 是使用上述貪婪準則得到的解, \mathscr {Y} = \left \{ y_{1}, y_{2}, ..., y_{n} \right \} 是任意一個可行解, 其中, x_{c}y_{c} 滿足

x_{c} = y_{c} = \begin {cases} 0 & {第 c 個箱子未被裝載} \\ 1 & {第 c 個箱子被裝載} \end {cases}, c = 1, 2, ..., n

由條件已知, 存在某個 k (0 \leq k \leq n), 使得當 i \leq k 時, 有 x_{k} = 1; 當 i > k 時, 有 x_{k} = 0

j = \min \left \{ i : x_{i} = 1 \right \}. 當 j = 1 時, 任意可行解 \mathscr {Y} 滿足 \mathscr {Y} \subset \mathscr {X}. 否則, \sum \limits_{i = 1}^{n} y_{i} > M. 其中, M 為最大裝載量. 此時 \mathscr {Y} 不是一個可行解. 自然地,

\sum \limits_{i = 1}^{n} x_{i} \geq \sum \limits_{i = 1}^{n} y_{i} \sum \limits_{i = 1}^{n} x_{i} \cdot w_{i} \geq \sum \limits_{i = 1}^{n} y_{i} \cdot w_{i}

j > 1 時, 任取正整數 m, 不妨設 j \leq m 時, 有 \sum \limits_{i = 1}^{n}x_{i}w_{i} \geq \sum \limits_{i = 1}^{n} y_{i}w_{i} 成立

j = m + 1 時, 令 y_{1} = 1, y_{j} = 0, y_{i} = x_{i} (i \neq j, i = 2, 3, ..., n)

\sum \limits_{i = 1}^{n}y_{i}w_{i} = w_{1} - w_{j} + \sum \limits_{i = 1}^{n}w_{i}x_{i}

由於 w_{j} \geq w_{1}, 因此 \sum \limits_{i = 1}^{n}y_{i}w_{i} \leq \sum \limits_{i = 1}^{n}w_{i}x_{i}. 另外, \sum \limits_{i = 1}^{n}x_{i} = \sum \limits_{i = 1}^{n}y_{i}

最後, 考慮 j = 0 的情況, 此時 \sum \limits_{i = 1}^{n}x_{i} = \sum \limits_{i = 1}^{n}y_{i} = 0, \sum \limits_{i = 1}^{n}x_{i}w_{i} = \sum \limits_{i = 1}^{n}y_{i}w_{i} = 0. 於是,

\sum \limits_{i = 1}^{n}x_{i} \geq \sum \limits_{i = 1}^{n}y_{i}\sum \limits_{i = 1}^{n}x_{i}w_{i} \geq \sum \limits_{i = 1}^{n}y_{i}w_{i}

綜上所述, 在任何情況下, \mathscr {X} 都是最佳解. 因此, 使用貪婪演算法產生的解是最佳解

證畢

為什麼要研究這兩個問題呢? 在作業系統中, CPU 排程問題實際上就是任務排程問題, 記憶體載入問題實際上就是箱櫃裝載問題

最後, 我們來分析所有貪婪演算法的時間複雜度. 我們暫時選取以最先適配遞減作為貪婪準則的貪婪演算法. 首先將物品進行排序, 如果我們用我們已經學習過的排序演算法, 那麼時間複雜度至少為 \Theta(n^{2}). 將所有物品裝載到箱櫃需要 O(n) 的時間複雜度. 剩下的都是一些輔助性的操作, 因此我們可以大致認為以最先適配遞減作為貪婪準則的貪婪演算法的時間複雜度為 O(n^{2}). 根據 P 問題與 NP 問題的定義, 任務排程問題和箱櫃裝載問題是 NP 問題的同時也都是 P 問題, 也就是對於這兩個問題, 有 P = NP 成立 (不表示 P = NP 對其它問題也成立). 以相鄰適配法則作為貪婪準則的貪婪演算法具有更佳的時間複雜度, 但是由於所需要的資料結構我們暫時沒講, 所以我們此處暫時不進行分析