「貪婪演算法(greedy algorithm / greedy method)」指的是依照每個步驟「當下」的狀況找到最佳解,但若從大局來看,可能不是最佳的解決方案。
現假設要在下圖中,找出從 A 走到 D 的最短路徑:
根據「貪婪演算法」,從 A 出發時最短路徑長為 2,取該路徑到 B;從 B 離開時最短路徑長為 1,取該路徑到 C;從 C 離開時唯一的選擇路徑長為 3,取該路徑到 D,最短路徑為 A→B→C→D,總路徑長為 2+1+3=6,但若從大局來看(例如利用「Dijkstra 演算法」),可發現 A 到 D 的最短路徑長應為 5。
範例一:Job Sequencing with Deadlines
現有一工作列表,表中資訊包含完成每個項目的獲利(profit)與截止日期(deadline),假設有 D1、D2、D3、D4 個工作天,試安排每天的工作項目,使獲利最大化。
步驟:
- 獲利最大者為 J4,且截止日為 D1,故將 J4 安排在 D1。
- 獲利次大者為 J1,截止日為 D3,雖也可安排在 D2,但為了讓 D2 可用來做其他事情,故將 J1 安排在 D3。
- 獲利第三大者為 J2,截止日為 D2,故將 J2 安排在 D2。
- 獲利第四大者為 J3,但 J3 的截止日為 D3,無法安排進 D4,因此捨棄 J3,改選獲利第五大、且截止日在 D4 的 J5 至 D4 中。
範例二:Fractional Knapsack Problem
假設有一背包,最多可裝 15 公斤的物品,現有各物品與其價值(value)、重量(weight)資訊列表如下:
試在未超重的情況下,使背包中所裝物品的價值為最高。與「0/1 背包問題(0/1 Knapsack problem)」不同的是,每項物品可以僅取其中一部分。
步驟:
- 計算各物品每重量單位的價值。
- 選擇每重量單位價值最高的 A,目前價值為 30、仍有 13 公斤可用。
- 選擇每重量單位價值次高的 E,目前價值為 40、仍有 12 公斤可用。
- 選擇每重量單位價值第三高的 D,目前價值為 85、仍有 7 公斤可用。
- 選擇每重量單位價值第四高的 C,目前價值為 97、仍有 4 公斤可用。
- 選擇每重量單位價值第五高的 B,但因僅剩 4 重量單位可用,因此僅取 B 的 4/6,價值為 12,總價值為 109,至此 15 公斤的背包全部裝滿,且裝的物品為價值最高的組合。