《算法图解》-C8贪婪算法

一、贪婪算法

贪婪算法又称贪心算法。
贪婪算法通过寻找局部最优解，来达到全局最优解。
贪婪算法是一种近似算法。
贪婪算法的运行时间为O(n2)

狄克斯特拉算法都是贪婪算法，快速排序不是贪婪算法。

演示问题的提出：
假设要办一个让美国50个州的听众都收听到的广播节目。
由于每个广播台只能覆盖特定的区域（不同广播台的覆盖区域可能重叠），
考虑到要尽量减少播放费用，所以要找出能覆盖全美50个州的最小广播台集合（即广播台数量尽量少）。

广播台覆盖问题

代码示例如下：

#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_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_needed - states_covered

# 局部最优解：添加：此次循环中覆盖最多州的广播台到列表中

final_stations.add(best_station)

# 输出结果

print(final_stations)

代码说明：
代码中使用了集合运算。

| 表示并集

& 表示交集

- 表示差集

集合中的数据顺序是无关的，{'a', 'b', 'c'} 与 {'c', 'a', 'b'} 是相等的。

s1 = set(['a', 'b', 'c', 'd'])

s2 = set(['b', 'c', 'd','e'])

print(s1 | s2) # {'d', 'a', 'c', 'b', 'e'}

print(s1 & s2) # {'b', 'c', 'd'}

print(s1 - s2) # {'a'} 要注意差集操作的集合对象顺序

print(s2 - s1) # {'e'}

二、NP完全问题

NP完全问题（NP-complete problems，NP-C问题）是世界七大数学难题之一。
NP完全问题目前还没有找到快速解决方案。[1]
旅行商问题和集合覆盖问题都是NP完全问题。

如何判断问题是不是NP完全问题？答案是没有办法！
如果元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。通常是NP完全问题。
如果问题可转换为集合覆盖问题或旅行商问题，则此问题是NP完全问题
如：邮差给N个家庭送信的最短路径；在一堆人中找出最大的朋友圈（即其中任何两个人都相识）
面临NP完全问题时，最佳的做法是使用近似算法（approximation algorithm）。