算法圖解第八章貪婪算法

貪婪算法:每步的局部最優解,可能是全局最優解。

問題1：有幾個廣播台，每個廣播台都覆寫特定的區域，不同的廣播台的覆寫區域可能重疊。找出覆寫全美50個州的最小廣播台集合。

1）選出這樣一個廣播台，即它覆寫了最多的未覆寫州。即便這個廣播台覆寫了一些已覆寫的州，也沒有關系。

2）重複第一步，直到覆寫了所有的州。

這個執行個體中，貪婪算法的時間複雜度為o（n^2）

python中集合類似于清單，隻是同樣的元素隻能出現一次，即集合不能包含重複的元素。

代碼執行個體：

# 首先，建立一個清單，其中包含要覆寫的州
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:
    best_station = None
    states_covered = set()
    # states_covered 是一個集合，包含該廣播台覆寫的所有未覆寫的州。for循環疊代每個廣播台，并确定它是否是最佳的廣播台。
    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_covered
    final_stations.add(best_station)
print(final_stations)
           

NP完全問題：

1）旅行商問題

旅行者需要前往5個不同的城市，他需要找出前往這5個城市的最短路徑

涉及兩個城市，可能的路線是2條

涉及三個城市，可能的路線是6條

涉及4個城市，可能的路線是24條

涉及n個城市，可能的路線是n！條

旅行商問題和集合覆寫問題有一些共同之處：你需要計算所有的解，并從中選出最小或者最短的那個。這兩個問題都屬于NP完全問題。

旅行商貪婪政策：随便選擇出發的城市，然後每次選擇要去的下一個城市時，都選擇還沒去過的最近的城市。

如何判斷問題是不是NP完全問題

1）元素較少時算法的運作速度非常快，但随着元素數量的增加，速度會變得非常慢。

2）涉及“所有組合”的問題通常是NP完全問題。

3）不能将問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。

4）如果問題涉及序列（如旅行商問題的城市序列）且難以解決，它可能就是NP完全問題。

5）如果問題涉及集合（如廣播集合）且難以解決，它可能就是NP完全問題。

6）如果問題可轉換為集合覆寫問題或者旅行商問題，那它肯定是NP完全問題。