第八章 貪婪算法

1　　簡(jiǎn)單的貪婪算法

每步都采取最優(yōu)的做法，每步都選擇局部最優(yōu)解。

---

2　　背包問(wèn)題

有些情況下，完美是優(yōu)秀的敵人。如果你只需要找到一個(gè)大致解決問(wèn)題的算法，貪婪算法挺不錯(cuò)，因?yàn)閷?shí)現(xiàn)容易，結(jié)果與正確結(jié)果相當(dāng)接近。

練習(xí)
8.1 你在一家家具公司工作，需要將家具發(fā)往全國(guó)各地，為此你需要將箱子裝上卡車(chē)。每個(gè)箱子的尺寸各不相同，你需要盡可能利用每輛卡車(chē)的空間，為此你將如何選擇要裝上卡車(chē)的箱子呢？請(qǐng)?jiān)O(shè)計(jì)一種貪婪算法。使用這種算法能得到最優(yōu)解嗎？

選擇可以裝入卡車(chē)中最大的箱子，不斷重復(fù)，直到不能再裝，這種算法得不到最優(yōu)解。

8.2 你要去歐洲旅行，總行程為7天。對(duì)于每個(gè)旅游勝地，你都給它分配一個(gè)價(jià)值——表示你有多想去那里看看，并估算出需要多長(zhǎng)時(shí)間。你如何將這次旅行的價(jià)值最大化？請(qǐng)?jiān)O(shè)計(jì)一種貪婪算法。使用這種算法能得到最優(yōu)解嗎？

不斷地挑選可以在剩下的時(shí)間內(nèi)完成的價(jià)值最大的活動(dòng)，知道剩下的時(shí)間不能夠完成任何活動(dòng)為止。同樣這種算法得不到最優(yōu)解。

---

3　　集合覆蓋問(wèn)題

假設(shè)你辦了個(gè)廣播節(jié)目，要讓全美50個(gè)州的聽(tīng)眾都收聽(tīng)得到。為此，你需要決定在哪些廣播臺(tái)播出。在每個(gè)廣播臺(tái)播出都需要支付費(fèi)用，因此你力圖在盡可能少的廣播臺(tái)播出。每個(gè)廣播臺(tái)都覆蓋特定的區(qū)域，不同廣播臺(tái)的覆蓋區(qū)域可能重疊。

具體方法如下：

①列出每個(gè)可能的廣播臺(tái)集合，這被稱為冪集（power set）。可能的子集有2**n個(gè)。

②在這些集合中，選出覆蓋全美50個(gè)州的最小集合。

由于可能的子集有2**n個(gè)，因此運(yùn)行時(shí)間為O(2**n)。

用貪婪算法可得到非常接近的解：

①選出這樣一個(gè)廣播臺(tái)，它覆蓋了最多的未覆蓋的州。即使有重復(fù)的州也沒(méi)有關(guān)系

②重復(fù)第一步，直到覆蓋了所有的州

這是一種近似算法。判斷近似算法優(yōu)劣的標(biāo)準(zhǔn)如下：

①速度有多快

②得到的近似解與最優(yōu)解的接近程度。在這個(gè)例子中貪婪算法的運(yùn)行時(shí)間為O（n**2）

---

上述問(wèn)題代碼實(shí)現(xiàn)過(guò)程（簡(jiǎn)化問(wèn)題）：

①準(zhǔn)備工作，首先，創(chuàng)建一個(gè)列表，其中包含要覆蓋的州：states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])（使用集合的不重復(fù)特點(diǎn)）；還需要有可供選擇的廣播清單，用散列表來(lái)表示它：

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"])

其中，鍵為電臺(tái)名字，值為覆蓋的州。最后用一個(gè)集合來(lái)保存最終選擇的電臺(tái)：final_stations = set()

②計(jì)算答案

需要從中選擇覆蓋了最多的未覆蓋州的廣播臺(tái)。將整個(gè)廣播臺(tái)存儲(chǔ)在best_station 中。

states_needed = (["mt", "wa", "or", "id", "nv", "ut","ca", "az"])　　　　#這個(gè)代碼有問(wèn)題沒(méi)解決
stations = {}
stations["kone"] = (["id", "nv", "ut"])
stations["ktwo"] = (["wa", "id", "mt"])
stations["kthree"] = (["or", "nv", "ca"])
stations["kfour"] = (["nv", "ut"])
stations["kfive"] = (["ca", "az"])
final_stations = ()
while states_needed:
    best_station = ()
    states_covered = ()
    for station, states_for_station in stations.items():
        covered = states_needed and 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)　　　　　　#這是結(jié)果set(['ktwo', 'kthree', 'kone', 'kfive'])

states_covered 是一個(gè)集合，包含該廣播臺(tái)覆蓋的所有未覆蓋的州。 for 循環(huán)迭代每個(gè)廣播臺(tái)，并確定它是否是最佳的廣播臺(tái)。下面來(lái)看看這個(gè) for 循環(huán)的循環(huán)體。

covered 是一個(gè)集合，包含同時(shí)出現(xiàn)在 states_needed 和states_for_station 中的州；

貪婪算法和精確算法的運(yùn)行時(shí)間對(duì)比：

練習(xí)
下面各種算法是否是貪婪算法。
8.3 快速排序。否
8.4 廣度優(yōu)先搜索。是
8.5 狄克斯特拉算法。是

---

4　　NP完全問(wèn)題

旅行商問(wèn)題詳解：

2個(gè)城市時(shí)，2條；3個(gè)城市時(shí)，6條；4個(gè)城市時(shí)，24條；同理：N個(gè)城市就是N！條，這被稱為階乘函數(shù)。

如何識(shí)別NP完全問(wèn)題：

①元素較少時(shí)算法的運(yùn)行速度非常快，但隨著元素?cái)?shù)量的增加，速度會(huì)變得非常慢。

②涉及“所有組合”的問(wèn)題通常是NP完全問(wèn)題。

③不能將問(wèn)題分成小問(wèn)題，必須考慮各種可能的情況。這可能是NP完全問(wèn)題。

④如果問(wèn)題涉及序列（如旅行商問(wèn)題中的城市序列）且難以解決，它可能就是NP完全問(wèn)題。

⑤如果問(wèn)題涉及集合（如廣播臺(tái)集合）且難以解決，它可能就是NP完全問(wèn)題。

⑥如果問(wèn)題可轉(zhuǎn)換為集合覆蓋問(wèn)題或旅行商問(wèn)題，那它肯定是NP完全問(wèn)題。

練習(xí)
8.6 有個(gè)郵遞員負(fù)責(zé)給20個(gè)家庭送信，需要找出經(jīng)過(guò)這20個(gè)家庭的最短路徑。請(qǐng)問(wèn)這是一個(gè)NP完全問(wèn)題嗎？類(lèi)似旅行商問(wèn)題，是一個(gè)NP完全問(wèn)題

8.7 在一堆人中找出最大的朋友圈（即其中任何兩個(gè)人都相識(shí)）是NP完全問(wèn)題嗎？類(lèi)似集合覆蓋問(wèn)題，同樣是一個(gè)NP完全問(wèn)題

8.8 你要制作美國(guó)地圖，需要用不同的顏色標(biāo)出相鄰的州。為此，你需要確定最少需要使用多少種顏色，才能確保任何兩個(gè)相鄰州的顏色都不同。請(qǐng)問(wèn)這是NP完全問(wèn)題嗎？也是

---

5　　小結(jié)

貪婪算法尋找局部最優(yōu)解，企圖以這種方式獲得全局最優(yōu)解。

對(duì)于NP完全問(wèn)題，還沒(méi)有找到快速解決方案。

面臨NP完全問(wèn)題時(shí)，最佳的做法是使用近似算法。

貪婪算法易于實(shí)現(xiàn)、運(yùn)行速度快，是不錯(cuò)的近似算法。

總結(jié)

以上是生活随笔為你收集整理的《算法图解》——第八章 贪婪算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。