摘要訊息 : 使用貪婪演算法解任務排程問題和箱櫃裝載問題.

0. 前言

在《貪婪演算法》中我們介紹了 NP 問題的實用定義, 本文將嘗試從貪婪演算法的角度分析任務排程問題和使用貪婪演算法解決箱櫃裝載問題.

本文在 2022 年 5 月 16 日进行一次更新和修正. 修正之后本文已经归档, 不再享受更新.

1. 任務排程

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

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

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

在作業系統中, CPU 排程問題實際上就是任務排程問題.

2. 箱櫃裝載

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

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

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. ...

斷言 1. 在箱櫃裝載問題中, 將方案 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} 滿足 \displaystyle {x_{c}, y_{c} = \begin {cases} 0 & {\text {第 } c \text{ 個箱子未被裝載}} \\ 1 & {\text {第 } c \text{ 個箱子被裝載}} \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, i = 1, 2, ..., n \right \}. 當 j = 1 時, 任意可行解 \mathscr {Y} 滿足 \mathscr {Y} \subset \mathscr {X}. 否則, \sum \limits_{i = 1}^{n} y_{i} > M (M 為最大裝載量), 此時 \mathscr {Y} 不是一個可行解. 自然地, 有 \displaystyle {\sum \limits_{i = 1}^{n} x_{i} \geq \sum \limits_{i = 1}^{n} y_{i} \text { 且 } \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), 那麼 \displaystyle {\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}, 因此 \displaystyle {\sum \limits_{i = 1}^{n}y_{i}w_{i} \leq \sum \limits_{i = 1}^{n}w_{i}x_{i}}. 另外, 又有 \displaystyle {\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. 於是, \displaystyle {\sum \limits_{i = 1}^{n}x_{i} \geq \sum \limits_{i = 1}^{n}y_{i} \text { 且 } \sum \limits_{i = 1}^{n}x_{i}w_{i} \geq \sum \limits_{i = 1}^{n}y_{i}w_{i}}.

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

\blacksquare

在作業系統中, 記憶體載入問題實際上就是箱櫃裝載問題.

我們暫時選取以最先適配遞減作為貪婪準則的貪婪演算法. 首先將物品進行排序, 如果我們用我們已經學習過的排序演算法, 那麼時間複雜度為 \Theta(n\log {n}). 將所有物品裝載到箱櫃需要 O(n) 的時間複雜度. 剩下的都是一些輔助性的操作, 因此我們可以大致認為以最先適配遞減作為貪婪準則的貪婪演算法的時間複雜度為 \Theta(n\log {n}). 根據 P 問題與 NP 問題的定義, 箱櫃裝載問題是 P 問題.