代碼小工蟻的#《算法圖解》#學習筆記-C8貪婪算法
C8 貪婪算法greedy algorithms
一蚌卤、貪婪算法
貪婪算法又稱貪心算法。
貪婪算法通過尋找局部最優(yōu)解炮叶，來達到全局最優(yōu)解续镇。
貪婪算法是一種近似算法镀裤。
貪婪算法的運行時間為O(n2)
狄克斯特拉算法都是貪婪算法，快速排序不是貪婪算法僚害。
演示問題的提出：
假設要辦一個讓美國50個州的聽眾都收聽到的廣播節(jié)目硫椰。
由于每個廣播臺只能覆蓋特定的區(qū)域（不同廣播臺的覆蓋區(qū)域可能重疊），
考慮到要盡量減少播放費用萨蚕，所以要找出能覆蓋全美50個州的最小廣播臺集合（即廣播臺數(shù)量盡量少）最爬。
廣播臺覆蓋問題
代碼示例如下：
#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()
# 判斷：是不是需要覆蓋的州都已覆蓋
# （為空，則表示已完成全部覆蓋门岔，循環(huán)結束）
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
# 局部最優(yōu)解：添加：此次循環(huán)中覆蓋最多州的廣播臺到列表中
final_stations.add(best_station)
# 輸出結果
print(final_stations)
代碼說明：
代碼中使用了集合運算。
| 表示并集
& 表示交集
- 表示差集
集合中的數(shù)據(jù)順序是無關的寒随，{'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問題）是世界七大數(shù)學難題之一互艾。
NP完全問題目前還沒有找到快速解決方案。[1]
旅行商問題和集合覆蓋問題都是NP完全問題讯泣。
如何判斷問題是不是NP完全問題纫普？答案是沒有辦法！
如果元素較少時算法的運行速度非澈们快昨稼，但隨著元素數(shù)量的增加，速度會變得非常慢拳锚。通常是NP完全問題假栓。
如果問題可轉換為集合覆蓋問題或旅行商問題，則此問題是NP完全問題
如：郵差給N個家庭送信的最短路徑霍掺；在一堆人中找出最大的朋友圈（即其中任何兩個人都相識）
面臨NP完全問題時匾荆，最佳的做法是使用近似算法（approximation algorithm）拌蜘。
[1]百度百科：NP完全問題
