【算法图解】近似算法

NP完全问题

NP完全问题的定义就是以难解著称的问题，如旅行商问题和集合覆盖问题。很多人认为不可能编出快速解决这类问题的算法。

NP完全问题有以下几个特点：

• 元素较少时算法运行速度非常快，随着元素增加，要考虑的情况急速增多，运行速度非常慢。
• 涉及“所有组合”的问题通常是NP完全问题。
• 不能将问题分成小问题，必须考虑各种可能的情况，这是通常是NP完全问题。
• 问题涉及序列且难以解决，可能是NP完全问题。
• 问题涉及集合且难以解决，可能是NP完全问题。
• 问题可转换为集合覆盖问题和旅行商问题，肯定是NP完全问题。

虽然不能完美得解决这类问题，但是可以优秀得解决这类问题。通常使用的算法就是近似算法。

贪婪算法

贪婪算法是一种比较典型的近似算法。

原理很简单：

1. 找出最合适的。
2. 找出第二合适的。
3. 直到不能满足限定要求

集合覆盖问题

如果有几个广播站可以覆盖一些地区，可能有重合，如何用最少的广播站覆盖最多的地区？

使用贪婪算法可以得到非常近似最优解的解。

1. 选出一个广播台，它覆盖了最多未覆盖的州。即使这个广播台覆盖了一些已经覆盖的州也没关系。
2. 重复第一步。

算法运行时间为O(n^2), n为广播台数量。

代码表现

# 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_station = set() #最终选择广播台

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_station.add(best_station)

print final_station

得到结果set(['ktwo', 'kthree', 'kone', 'kfive'])