算法圖解第八章筆記與習題（貪婪算法）

文章目錄

• 算法圖解第八章筆記與習題（貪婪算法）
• • 8.1 貪婪算法
  • 8.2 集合覆寫問題
  • 8.3 NP完全問題
  • • 8.3.1 旅行商問題：
    • 8.3.2 如何識别NP完全問題
    • 8.4 小結
  • 練習
  • • 習題8.1：
    • • 習題8.2：
      • 習題8.3-5題幹：
      • 習題8.3：
      • 習題8.4：
      • 習題8.5：
      • 習題8.6：
      • 習題8.7：
      • 習題8.8：

算法圖解pdf百度雲連結，提取碼：jttg

8.1 貪婪算法

貪婪算法：對于一個問題，根據問題要求的目标，每步都選擇局部最優解。在某些特定的情況下，貪婪算法能夠得到最優解，但通常隻能能夠得到一個接近最優解的解。

舉例：從十個數中選擇五個使其和最大

1,2,3,4,5,6,7,8,9,10

。

根據問題要求的目标（和最大），每步都選擇局部最優解（從未被選擇的數中選擇最大的那個數）。對于這個簡單的情況來說，貪婪算法将得到最優解

10+9+8+7+6=40

。但對于更複雜的情況來說，通常會得到一個接近最優解的解。

8.2 集合覆寫問題

假設現在有個廣播節目，要讓全美國50個州的聽衆都收聽得到，為此，需要決定在哪些廣播台播出。在每個廣播台播出都需要支付費用，是以必須在盡可能少的廣播台播出。現有廣播台名單如下：

每個廣播台都覆寫特定的區域，不同廣播台的覆寫區域可能重疊。

那麼找出覆寫全美50個州的最小廣播台合集呢？下面是解決步驟：

1. 列出每個可能的廣播台集合，這被稱為幂集（power set）。可能的子集有 2 n 2^n 2n個。
2. 在這些集合中，選出覆寫全美50個州的最小集合。

這樣做固然能找到最優解，但其時間複雜度為 O ( 2 n ) O(2^n) O(2n)，其中n為廣播台數量。在這種情況下，我們可以使用貪婪算法來解決這個問題。步驟如下：

1. 選出這樣一個廣播台，即它覆寫了最多未覆寫的州。即便這個廣播台覆寫了一些已覆寫的州（就是重複覆寫），也沒有關系。
2. 重複第一步，直到覆寫了所有的州。

這是一種近似算法（approximation algorithm）。在獲得精确解需要的時間太長時，可以考慮使用近似算法。判斷近似算法優劣的标準如下：

• 速度有多快；
• 得到的近似解與最優解的接近程度。

是以貪婪算法是一個不錯的選擇，它們不僅簡單，而且通常運作速度很快。在本例中，貪婪算法的運作時間為 O ( n 2 ) O(n^2) O(n2)，其中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() # 使用一個集合來存儲最終選擇的廣播台
 
while states_needed:
  best_station = None # 将覆寫了最多的未覆寫州的廣播台存儲進去
  states_covered = set() # 一個集合，包含該廣播台覆寫的所有未覆寫的州
  for station, states in stations.items(): # 循環疊代每個廣播台并确定它是否是最佳的廣播台
    covered = states_needed & states # 計算交集
    if len(covered) > len(states_covered): # 檢查該廣播台的州是否比best_station多
      best_station = station # 如果多，就将best_station設定為目前廣播台
      states_covered = covered
 
  states_needed -= states_covered # 更新states_needed
  final_stations.add(best_station) # 在for循環結束後将best_station添加到最終的廣播台清單中
 
print(final_stations) # 列印final_stations
set(['ktwo', 'kthree', 'kone', 'kfive'])
#（算法也可以用未被覆寫的州來做比較，未被覆寫的州越少，則該廣播台是局部更優的廣播台。）
           

上述代碼中，

set()

是一種集合，類似于清單，但相同的元素在其中出現一次，也沒有索引供查找。

另外，還涉及到了數學中交集的計算

&

，以及集合間相見

-=

。具體不做詳細介紹。

使用上述貪婪算法的運作時間僅為 O ( n 2 ) O(n^2) O(n2)，比起周遊所有子集來獲得精确解的精确算法 O ( 2 n ) O(2^n) O(2n)來說非常快。

8.3 NP完全問題

8.3.1 旅行商問題：

旅行商問題是指，旅行商需要在一次旅行中途徑多個不同的城市，如何求解其最短路徑。

對于 1 個城市而言，僅有 1 條可能的路徑。

對于 2 個城市而言，有 2 個可能的起點X每個出發的城市1條可能的路徑 = 2條可能的路徑。

對于 3 個城市而言，有 3 個可能的起點X每個出發的城市2條可能的路徑 = 6條可能的路徑。

對于 4 個城市而言，有 4 個可能的起點X每個出發的城市6條可能的路徑 = 24條可能的路徑。

對于 5 個城市而言，有 5 個可能的起點X每個出發的城市24條可能的路徑 = 120條可能的路徑。

……

這是一個階乘函數（factorical function），當涉及的城市越多時，可能的路徑條數增加的非常快。是以當涉及的城市足夠多時，根本就難以計算出旅行商問題的正确解。

NP完全問題的簡單定義是，以難著稱的問題，如旅行商問題和集合覆寫問題。（？）

8.3.2 如何識别NP完全問題

NP完全問題無處不在！如果能夠判斷出要解決的問題屬于NP完全問題就好了，這樣就不用去尋找完美的解決方案，而是使用近似算法即可。但要判斷問題是不是NP完全問題很難，易于解決的問題和NP完全問題的差别通常很小。

但事實是沒辦法判斷問題是不是NP完全問題，但還是有迹可循的：

• 元素較少時算法的運作速度非常快，但随着元素數量的增加，速度會變得非常慢。
• 涉及“所有組合”的問題通常是NP完全問題。
• 不能将問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。
• 如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。
• 如果問題涉及集合（如廣播台集合）且難以解決，它可能就是NP完全問題。
• 如果問題可轉換為集合覆寫問題或旅行商問題，那它肯定是NP完全問題。

8.4 小結

• 貪婪算法尋找局部最優解，企圖以這種方式獲得全局最優解。
• 對于NP完全問題，還沒有找到快速解決方案。
• 面臨NP完全問題時，最佳的做法是使用近似算法。
• 貪婪算法易于實作、運作速度快，是不錯的近似算法。

練習

習題8.1：

• 你在一家家具公司工作，需要将家具發往全國各地，為此你需要将箱子裝上卡車。每個箱子的尺寸各不相同，你需要盡可能利用每輛卡車的空間，為此你将如何選擇要裝上卡車的箱子呢？請設計一種貪婪算法。使用這種算法能得到最優解嗎？

将剩餘箱子中最大的一個裝入箱子，直到将所有的箱子裝入卡車為止。使用這種算法不能找到最優解。

習題8.2：

• 你要去歐洲旅行，總行程為7天。對于每個旅遊勝地，你都給它配置設定一個價值——表示你有多想去那裡看看，并估算出需要多長時間。你如何将這次旅行的價值最大化？請設計一種貪婪算法。使用這種算法能得到最優解嗎？

從剩餘未去過的旅遊勝地中選擇價值最高的，直至時間用完為止。使用這種算法不能找到最優解。

習題8.3-5題幹：

• 下面各種算法是否是貪婪算法。

習題8.3：

• 快速排序。

不是。

習題8.4：

• 廣度優先搜尋。

是。

習題8.5：

• 狄克斯特拉算法。

是。

習題8.6：

• 有個郵差負責給20個家庭送信，需要找出經過這20個家庭的最短路徑。請問這是一 個NP完全問題嗎？

是。可轉化為旅行商問題。

習題8.7：

• 在一堆人中找出最大的朋友圈（即其中任何兩個人都相識）是NP完全問題嗎？

是。可轉化為集合覆寫問題。

習題8.8：

• 你要制作美國地圖，需要用不同的顔色标出相鄰的州。為此，你需要确定最少需要使用多少種顔色，才能確定任何兩個相鄰州的顔色都不同。請問這是NP完全問題嗎？

不是。（圖着色問題，是NP完全問題。）