實例：
假設你辦了個廣播節目，要讓全美50個州的聽眾都聽到。為次，你需要決定哪些廣播臺播出。在每個廣播臺播出都需要支付費用，因此你要盡可能少的在廣播臺播出。。

其中每個廣播臺覆蓋特定的區域，不同廣播臺的覆蓋區域可能重疊

這樣的話要遍歷所有的可能的子集合組合，就有2n，其中n為廣播臺數目，用大O表示法運行時間為O(2n)。如果廣播臺很多，就成了一個NP難問題，而貪婪算法可以得到非常接近的解：

選出這樣一個廣播臺，即它覆蓋了最多的州。即便這個廣播臺覆蓋了一些已覆蓋的州，也沒有關系

重復第一步，直到覆蓋所有的州

這是一種近似算法，因為獲得精確解需要的時間太長，而貪婪算法可以很好的近似。。
而貪婪算法的運行時間為O(n2)，減少的時間不止一點點。。

# coding=utf-8# 要覆蓋的州 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(): # items()存儲鍵值(廣播臺和相應的覆蓋州)covered = states_needed & states # 集合的交集，判斷還未覆蓋的州與此廣播臺的交集個數 if len(covered) > len(states_covered): # 如果當前廣播臺州交集的個數大于當前要覆蓋的州 best_station = station # 就替換為最優的廣播臺states_covered = covered # 替換已經覆蓋的州states_needed -= states_covered # 從要覆蓋的州中減去已經覆蓋過的(集合相減)print 'states_needed:',states_neededfinal_stations.add(best_station) # 添加最優的廣播臺print final_stations

結果：

========== RESTART: C:\Users\LiLong\Desktop\Algorithm\set_cover.py ========== states_needed: set(['ut', 'ca', 'az', 'or', 'nv']) states_needed: set(['ut', 'az']) states_needed: set(['ut']) states_needed: set([]) set(['ktwo', 'kthree', 'kone', 'kfive']) >>>

得到了最終選的廣播臺集合是：’ktwo’, ‘kthree’, ‘kone’, ‘kfive’這4個

這只是個很簡單的NP難得例子，還有其他的很多，有待進一步學習。。

參考：《算法圖解》

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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