貪婪演算法(Greedy Algorithm)


「貪婪演算法(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 個工作天,試安排每天的工作項目,使獲利最大化。

步驟:

  1. 獲利最大者為 J4,且截止日為 D1,故將 J4 安排在 D1。
  2. 獲利次大者為 J1,截止日為 D3,雖也可安排在 D2,但為了讓 D2 可用來做其他事情,故將 J1 安排在 D3。
  3. 獲利第三大者為 J2,截止日為 D2,故將 J2 安排在 D2。
  4. 獲利第四大者為 J3,但 J3 的截止日為 D3,無法安排進 D4,因此捨棄 J3,改選獲利第五大、且截止日在 D4 的 J5 至 D4 中。

範例二:Fractional Knapsack Problem

假設有一背包,最多可裝 15 公斤的物品,現有各物品與其價值(value)、重量(weight)資訊列表如下:

試在未超重的情況下,使背包中所裝物品的價值為最高。與「0/1 背包問題(0/1 Knapsack problem)」不同的是,每項物品可以僅取其中一部分。

步驟:

  1. 計算各物品每重量單位的價值。
  2. 選擇每重量單位價值最高的 A,目前價值為 30、仍有 13 公斤可用。
  3. 選擇每重量單位價值次高的 E,目前價值為 40、仍有 12 公斤可用。
  4. 選擇每重量單位價值第三高的 D,目前價值為 85、仍有 7 公斤可用。
  5. 選擇每重量單位價值第四高的 C,目前價值為 97、仍有 4 公斤可用。
  6. 選擇每重量單位價值第五高的 B,但因僅剩 4 重量單位可用,因此僅取 B 的 4/6,價值為 12,總價值為 109,至此 15 公斤的背包全部裝滿,且裝的物品為價值最高的組合。
#演算法 #貪婪演算法







你可能感興趣的文章

Angular 入門教學 - 系列文目錄

Angular 入門教學 - 系列文目錄

CSS split four squares

CSS split four squares

Command Line

Command Line






留言討論