一、貪婪算法
貪婪算法又稱貪心算法。
貪婪算法通過尋找局部最優解，來達到全局最優解。
貪婪算法是一種近似算法。
貪婪算法的運作時間為O(n2)
狄克斯特拉算法都是貪婪算法，快速排序不是貪婪算法。
示範問題的提出：
假設要辦一個讓美國50個州的聽衆都收聽到的廣播節目。
由于每個廣播台隻能覆寫特定的區域（不同廣播台的覆寫區域可能重疊），
考慮到要盡量減少播放費用，是以要找出能覆寫全美50個州的最小廣播台集合（即廣播台數量盡量少）。
廣播台覆寫問題
代碼示例如下：
#coding=utf-8
# 貪婪算法示範
# 需要覆寫的州
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()
# 判斷：是不是需要覆寫的州都已覆寫
# （為空，則表示已完成全部覆寫，循環結束）
while 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
# 差集：需要覆寫的州 減去 已覆寫的州
# 得到：還未覆寫的州
# 不斷縮小，達到全部覆寫（集合為空）
states_needed = states_needed - states_covered
# 局部最優解：添加：此次循環中覆寫最多州的廣播台到清單中
final_stations.add(best_station)
# 輸出結果
print(final_stations)
代碼說明：
代碼中使用了集合運算。
| 表示并集
& 表示交集
- 表示差集
集合中的資料順序是無關的，{'a', 'b', 'c'} 與 {'c', 'a', 'b'} 是相等的。
s1 = set(['a', 'b', 'c', 'd'])
s2 = set(['b', 'c', 'd','e'])
print(s1 | s2) # {'d', 'a', 'c', 'b', 'e'}
print(s1 & s2) # {'b', 'c', 'd'}
print(s1 - s2) # {'a'} 要注意差集操作的集合對象順序
print(s2 - s1) # {'e'}
二、NP完全問題
NP完全問題（NP-complete problems，NP-C問題）是世界七大數學難題之一。
NP完全問題目前還沒有找到快速解決方案。[1]
旅行商問題和集合覆寫問題都是NP完全問題。
如何判斷問題是不是NP完全問題？答案是沒有辦法！
如果元素較少時算法的運作速度非常快，但随着元素數量的增加，速度會變得非常慢。通常是NP完全問題。
如果問題可轉換為集合覆寫問題或旅行商問題，則此問題是NP完全問題
如：郵差給N個家庭送信的最短路徑；在一堆人中找出最大的朋友圈（即其中任何兩個人都相識）
面臨NP完全問題時，最佳的做法是使用近似算法（approximation algorithm）。
掃碼關注本人微信公衆号，有驚喜奧！公衆号每天定時發送精緻文章！回複關鍵詞可獲得海量各類程式設計開發學習資料！
例如：想獲得Python入門至精通學習資料，請回複關鍵詞Python即可。