《演算法圖解》筆記(7) 貪心演算法
貪婪演算法
貪婪演算法的優點——簡單易行!貪婪演算法很簡單:每步都採取最優的做法。用專業術語說,就是你每步都選擇區域性最優解,最終得到的就是全域性最優解。
集合覆蓋問題
假設你辦了個廣播節目,要讓全美50個州的聽眾都收聽得到。你需要決定在哪些廣播臺播出。力圖在儘可能少的廣播臺播出。每個廣播臺都覆蓋特定的區域,不同廣播臺的覆蓋區域可能重疊。
如何找出覆蓋全美50個州的最小廣播臺集合呢?具體方法如下:
- 列出每個可能的廣播臺集合,這被稱為冪集(power set)。可能的子集有2n 個。
- 在這些集合中,選出覆蓋全美50個州的最小集合。
貪婪演算法可化解危機!使用下面的貪婪演算法可得到非常接近的解。
- 選出這樣一個廣播臺,即它覆蓋了最多的未覆蓋州。即便這個廣播臺覆蓋了一些已覆蓋的州,也沒有關係。
- 重複第一步,直到覆蓋了所有的州。
這是一種近似演算法(approximation algorithm)。在獲得精確解需要的時間太長時,可使用近似演算法。判斷近似演算法優劣的標準如下:
- 速度有多快;
- 得到的近似解與最優解的接近程度。
貪婪演算法是不錯的選擇,它們不僅簡單,而且通常執行速度很快。在這個例子中,貪婪演算法的執行時間為 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() #迴圈,直到states_needed為空 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_covered final_stations.add(best_station) print(final_stations)
NP 完全問題
NP(Non-Deterministic Polynomial, 非確定多項式)問題。
P問題:一個問題可以在多項式(O(n^k))的時間複雜度內解決。
NP問題 : 一個問題的解可以在多項式的時間內被驗證。
NP-hard問題 : 任意np問題都可以在多項式時間內歸約為該問題,但該問題本身不一定是NP問題。歸約的意思是為了解決問題A,先將問題A歸約為另一個問題B,解決問題B同時也間接解決了問題A。
NPC問題:既是NP問題,也是NP-hard問題。
判斷NP完全問題
1.元素較少時演算法的執行速度非常快,但隨著元素數量的增加,速度會變得非常慢。
2.涉及“所有組合”。
3.不能將問題分成小問題,必須考慮各種可能的情況。
4.如果問題涉及序列(如旅行商問題中的城市序列)且難以解決。
5.如果問題涉及集合(如廣播臺集合)且難以解決。
6.如果問題可轉換為集合覆蓋問題或旅行商問題。
小結
- 貪婪演算法尋找區域性最優解,企圖以這種方式獲得全域性最優解。
- 對於NP完全問題,還沒有找到快速解決方案。
- 面臨NP完全問題時,最佳的做法是使用近似演算法。
- 貪婪演算法易於實現、執行速度快,是不錯的近似演算法。
小貼士
集合, 集合類似於列表,只是同樣的元素只能出現一次,即集合不能包含重複的元素 .
>>>arr = [1, 2, 2, 3, 3, 3]
並且你將其轉換為集合。
>>> set(arr)
set([1, 2, 3])
>>> fruits | vegetables 並集
>>>fruits & vegetables 交集
分類 就是編組。
迴歸 就是預測結果(如一個數字)。
對映函式
>>> arr1 = [1, 2, 3, 4, 5]
>>> arr2 = map(lambda x: 2 * x, arr1)
[2, 4, 6, 8, 10]