前言
- 貪婪算法：每步都采取最優的做法。每步都選擇局部最優解，企圖以這種方式獲得全局最優解；
- 面臨NP完全問題，最佳的做法是使用近似算法；
- 貪婪算法易于實作、運作速度快，是不錯的近似算法。
-
判斷近似算法優劣的标準如下：
速度有多快；
得到的近似解與最優解的接近程度。
NP完全問題
NP完全問題（Non-deterministic Polynomial），即多項式複雜程度的非确定性問題。
1. 集合覆寫問題
為解決集合覆寫問題，你必須計算每個可能的集合。
2. 旅行商問題
旅行商需要前往5個不同的城市，需要找出前往這5個城市的最短路徑，為此，必須計算每條可能的路徑。
旅行商問題和集合覆寫問題有一些共同之處：你需要計算所有的解，并從中選出最小/最短的那個。這兩個問題都屬于NP完全問題。
NP完全問題共同特征：
元素較少時算法的運作速度非常快，但随着元素數量的增加，速度會變得非常慢。
涉及“所有組合”的問題通常是NP完全問題。
不能将問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。
如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。
如果問題涉及集合（如廣播台集合）且難以解決，它可能就是NP完全問題。
如果問題可轉換為集合覆寫問題或旅行商問題，那它肯定是NP完全問題。
近似算法
解決一個集合覆寫問題：盡可能少的廣播台覆寫全美50個州，每個廣播台都覆寫特定的區域，不同廣播台的覆寫區域可能重疊。
(1) 列出每個可能的廣播台集合，這被稱為幂集（power set）。可能的子集有 2 n 2^n 2n個。
(2) 在這些集合中，選出覆寫全美50個州的最小集合。
這種解決方案運作時間為O( 2 n 2^n 2n)，随着廣播台的增多，需要的時間将激增。沒有任何算法可以足夠快地解決這個問題！
貪婪算法可得到非常接近的解。
(1) 選出這樣一個廣播台，即它覆寫了最多的未覆寫州。即便這個廣播台覆寫了一些已覆寫的州，也沒有關系。
(2) 重複第一步，直到覆寫了所有的州。
在這個例子中，貪婪算法的運作時間為O( n 2 n^2 n2)，其中 n n n為廣播台數量。
代碼如下：
#用集合來表示要覆寫的州，傳入一個資料，它被轉換為集合
states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])
#用散清單表示可供選擇的廣播台清單
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
#用一個集合來存儲最終選擇的廣播台
final_stations = set()
#周遊所有的廣播台，從中選擇覆寫最多未覆寫州的廣播台，将這個廣播台存儲在best_station中
while states_needed: #直到states_needed為空
best_station = None
states_covered = set() #包含該廣播台覆寫的所有未覆寫的州
for station, states_for_station in stations.items():
covered = states_needed & states_for_station #計算交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
final_stations.add(best_station)
states_needed -= states_covered
print final_stations