常用编程思想与算法(5)

  这就是贪婪算法。虽然贪婪算法是万能的但是他往往不是最优的,但是对于一些没有更好的解决方法,贪婪算法往往是最有效的。

  集合覆盖问题

  假设你办了一个电视节目你想在全国上映,但是每个电视台覆盖的范围都不一样,还可能有重复覆盖的区域。

常用编程思想与算法

  (1) 列出每个可能的广播台集合,这被称为幂集(power set)。可能的子集有2n个。

  (2) 在这些集合中,选出覆盖全美50个州的最小集合。问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2**n个,因此运行时间为 O(2**n )。

常用编程思想与算法

  贪婪算法可化解危机!使用下面的贪婪算法可得到非常接近的解。

  (1) 选出这样一个广播台,即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州,也没有关系。

  (2) 重复第一步,直到覆盖了所有的州。

  这是一种近似算法(approximation algorithm)。在获得精确解需要的时间太长时,可使用近似算法。

  判断近似算法优劣的标准如下:

   速度有多快;

   得到的近似解与最优解的接近程度。

  这个问题的算法代码:

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(): 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) 运行结果; {'kone', 'ktwo', 'kthree', 'kfive'}

  贪婪算法还可以求出旅行商问题的简单答案。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/2d65c1b989daf15163eb8d959b598d3f.html