3.集合覆蓋問題
現(xiàn)在有個廣播節(jié)目机打，需要讓全美50個州的聽眾收聽。每個廣播臺都覆蓋特定的區(qū)域片迅，不同廣播臺覆蓋區(qū)域可能重疊残邀。如何找出覆蓋全美50個州的最小波廣播臺集合呢？
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 列表包含要覆蓋的州
stations = {} #記錄每個廣播臺對應(yīng)的州
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() # 最終選擇的廣播臺
best_station = None # 每次遍歷時(shí)覆蓋最多個州的廣播臺
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
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 = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
print(final_stations)
4.NP完全問題
簡單定義：需要計(jì)算所有的解柑蛇，并從中選出最小/最短的那個芥挣。如旅行商問題和集合覆蓋問題。
面對 NP 完全問題時(shí)唯蝶，最佳做法時(shí)使用近似算法九秀。
貪婪算法易于實(shí)現(xiàn)、運(yùn)行速度快粘我、是不錯的近似算法鼓蜒。
