怎么使用Python貪心算法解決集合覆蓋問題

本文小編為大家詳細(xì)介紹“怎么使用Python貪心算法解決集合覆蓋問題”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“怎么使用Python貪心算法解決集合覆蓋問題”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。

在《算法圖解》里面有一個(gè)蠻有意思的小案例，背景是一個(gè)廣播節(jié)目，要讓全美的50個(gè)周的聽眾都能夠聽到，但是每個(gè)電臺(tái)可能覆蓋多個(gè)州，每在一個(gè)電臺(tái)播出就需要一筆費(fèi)用，所以就是從成本的角度來看，怎么盡可能在所有的州都播出，這是一個(gè)典型的集合覆蓋的問題，而且在我們的生活中算是比較典型。

比如我們先縮小范圍，指定5個(gè)州，那么50個(gè)州也是同樣的算法。

states_need = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 傳入一個(gè)數(shù)組， 它被轉(zhuǎn)換為集合

有的同學(xué)可能對(duì)這些州沒概念，這個(gè)簡稱就跟京代表北京，魯代表山東，甘代表甘肅一樣，細(xì)細(xì)一看，都是西部的一些州。

如何使用貪心算法呢，就是選擇覆蓋盡可能多的州的電臺(tái)，然后逐步縮小范圍。那么覆蓋面廣的州所對(duì)應(yīng)的電臺(tái)就優(yōu)先被選中，依次類推。

程序的實(shí)現(xiàn)是指定了一個(gè)集合states_need，里面包含所有的州，每個(gè)電臺(tái)對(duì)應(yīng)的州是通過初始化的數(shù)組元素來實(shí)現(xiàn)的，按照一二三四五的順序來命名，當(dāng)然實(shí)際上這種元素的排列set不是按照數(shù)組名的順序，在這個(gè)場景里是kfive,ktwo,kthree,kone,kfour

然后逐步縮小范圍來收斂，里面比較特別的一點(diǎn)就是集合的運(yùn)算，使用了 & ,得到的是交集，如果是并集是 |，差集是 -，

程序代碼如下：

#!/usr/bin/env
 python# coding:utf-8states_need = set(["mt", "wa", "or", "id", "nv", 
"ut", "ca", "az"]) # 傳入一個(gè)數(shù)組， 它被轉(zhuǎn)換為集合# 可供選擇的廣播臺(tá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"])print(stations)# 最終選擇的廣播臺(tái)集合final_stations = set()while 
states_need:best_station = Nonestates_covered = set()for station, 
states_for_station in stations.items():covered = states_need & 
states_for_station # 
求交集print("states_need:",states_need,"states_for_station:",states_for_station,"covered:",covered)if
 len(covered) > len(states_covered):best_station = 
stationstates_covered = coveredstates_need -= 
states_coveredfinal_stations.add(best_station)print("states_needed:",states_need,"best_station:",best_station,"final_stations:",final_stations)print("---")print("Final_stations:",final_stations)

為了方便調(diào)試和得到一個(gè)迭代的結(jié)果，我加了幾處輸出日志，工參考。

{'kfive':
 set(['ca', 'az']), 'ktwo': set(['mt', 'id', 'wa']), 'kthree': 
set(['ca', 'or', 'nv']), 'kone': set(['ut', 'id', 'nv']), 'kfour': 
set(['ut', 'nv'])}('states_need:', set(['wa', 'ut', 'ca', 'id', 'mt', 
'az', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 
'covered:', set(['ca', 'az']))('states_needed:', set(['wa', 'ut', 'id', 
'mt', 'or', 'nv']), 'best_station:', 'kfive', 'final_stations:', 
set(['kfive']))---('states_need:', set(['wa', 'ut', 'id', 'mt', 'or', 
'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', 
set(['mt', 'id', 'wa']))('states_needed:', set(['ut', 'or', 'nv']), 
'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 
'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 
'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 
'nv']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 
'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', 
set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'id', 'nv']),
 'covered:', set(['ut', 'nv']))('states_needed:', set(['ut', 'or', 
'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 
'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 
'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut', 
'nv']))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 
'ktwo', 'final_stations:', set(['ktwo', 'kfive']))---('states_need:', 
set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 
'covered:', set([]))('states_needed:', set(['ut', 'or', 'nv']), 
'best_station:', None, 'final_stations:', set(['ktwo', None, 
'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 
'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', 
set([]))('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 
None, 'final_stations:', set(['ktwo', None, 
'kfive']))---('states_need:', set(['ut', 'or', 'nv']), 
'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 
'nv']))('states_needed:', set(['ut']), 'best_station:', 'kthree', 
'final_stations:', set(['ktwo', 'kthree', None, 
'kfive']))---('states_need:', set(['ut']), 'states_for_station:', 
set(['ut', 'id', 'nv']), 'covered:', set(['ut']))('states_needed:', 
set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 
'kthree', None, 'kfive']))---('states_need:', set(['ut']), 
'states_for_station:', set(['ut', 'nv']), 'covered:', 
set(['ut']))('states_needed:', set(['ut']), 'best_station:', 'kthree', 
'final_stations:', set(['ktwo', 'kthree', None, 
'kfive']))---('states_need:', set(['ut']), 'states_for_station:', 
set(['ca', 'az']), 'covered:', set([]))('states_needed:', set(['ut']), 
'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 
'kfive']))---('states_need:', set(['ut']), 'states_for_station:', 
set(['mt', 'id', 'wa']), 'covered:', set([]))('states_needed:', 
set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 
'kthree', None, 'kfive']))---('states_need:', set(['ut']), 
'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', 
set([]))('states_needed:', set(['ut']), 'best_station:', None, 
'final_stations:', set(['ktwo', 'kthree', None, 
'kfive']))---('states_need:', set(['ut']), 'states_for_station:', 
set(['ut', 'id', 'nv']), 'covered:', set(['ut']))('states_needed:', 
set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 
'kthree', None, 'kfive', 'kone']))---('states_need:', set([]), 
'states_for_station:', set(['ut', 'nv']), 'covered:', 
set([]))('states_needed:', set([]), 'best_station:', 'kone', 
'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 
'kone']))---('Final_stations:', set(['ktwo', 'kthree', None, 'kfive', 
'kone']))

最后的結(jié)果是：ktwo,kthree,kfive,kone這四個(gè)電臺(tái)。

讀到這里，這篇“怎么使用Python貪心算法解決集合覆蓋問題”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。