數據結構和算法
基于《算法圖解》—Aditya Bhargava 和《數據結構》—嚴蔚敏

第8章 貪婪算法

貪婪算法的優點： 簡單易行，讓每一步都選擇局部最優解，最終得到的就是全局最優解。
貪婪算法是近似算法：在獲得精確解需要的時間太長時，可以使用近似算法。

判斷近似算法優劣的標準如下：

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

8.1 集合覆蓋問題
例如解決經典的集合覆蓋問題——選擇最優的廣播電臺：
假設辦了個廣播節目，要讓全美50個州的聽眾都收聽得到。為此，需要決定在哪些廣播臺播出。在每個廣播臺播出都需要支付費用，因此，要盡可能少的廣播臺播出。

#首先創建一個列表，包含要覆蓋的州 states_needed = set(["mt", "wa", "id", "nv", "ut", "ca", "az"]) #傳入一個數組，它被轉換為集合。 #創建可供選擇的廣播臺清單，使用散列表表示。 station = {} station["kone"] = set(["id","nv","ut"]) station["ktwo"] = set(["wa","id","mt"]) station["kthree"] = set(["or","nv","ca"]) station["kfour"] = set(["nv","ut"]) station["kfive"] = set(["ca","az"]) #創建一個集合來存儲最終選擇的廣播臺。 final_station = set()#計算結果 while states_needed:best_staion = Nonestates_covered = set()for station, states in stations.items():covered = states_needed & states #計算交集if len(covered) > len(states_covered):best_station = stationstates_covered = coveredstates_needed -= states_coveredfinal_stations.add(best_station) print final_stations

8.2 NP完全問題
Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。

判斷NP完全問題的方法：

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

8.3 小結

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

——持續修改完善中…

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的08-贪婪算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。