已發布·持續改進
Algorithm
貪婪演算法在每一步都做出當下看來最好的選擇且不回頭，能快速解決區間排程、霍夫曼編碼與分數背包等問題。
貪婪演算法把問題拆成一連串的選擇，在每一步依照固定的規則挑出當下看起來最好的候選，而且不再修改這個決定。大多數貪婪演算法會先將候選排序或放入優先佇列，再逐一取出決定是否接受，因此程式碼簡短，時間複雜度通常由排序或堆積操作決定，為 O(n log n)。
貪婪演算法在適用的問題上是最快、最簡單的解法，但並非總是正確。要保證得到最佳解，必須同時滿足貪婪選擇性質與最佳子結構，通常以交換論證來證明。只要存在一個反例，例如用面額 1、3、4 的硬幣湊出 6，就表示需要改用動態規劃。霍夫曼編碼、Dijkstra 最短路徑與最小生成樹等廣泛使用的核心演算法，也都包含貪婪的思想。
學習時建議從區間排程（活動選擇）開始，試著用交換論證說明為什麼「選擇最早結束的活動」是正確的。接著親手實作霍夫曼編碼、分數背包以及用堆積完成的會議室分配，並養成在小規模輸入上與暴力搜尋比對結果的習慣，如此在程式面試與解題時就能迅速找出錯誤的貪婪策略。
必須存在一個包含第一次貪婪選擇的最佳解，這是貪婪演算法正確的核心條件。
證明把任意最佳解逐一替換為貪婪解中的元素不會變差，藉此說明貪婪規則是正確的。
依結束時間、單位重量價值或頻率將候選排序，或從堆積中取出，因此大多能在 O(n log n) 內完成。
對任意硬幣系統的找零或 0/1 背包，貪婪規則會出錯，此時應改用動態規劃。
這個程式挑出數量最多且互不重疊的會議。它先依結束時間將會議排序，只有當會議在上一個選中的會議結束之後才開始時才接受。排序需要 O(n log n)，掃描需要 O(n)；範例會從 11 場會議中選出 4 場。
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.py共六章，帶你從安裝一步步認識 貪婪演算法 的核心概念。
在這裡提問、分享經驗，交流關於 貪婪演算法 的看法。
還沒有討論。來發起第一則吧。
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。