算法图解第8章笔记

发表于

标签： 简单算法 笔记 python

贪婪算法思想：

每步都选择局部最优解，最终得到的就是全局最优解。

集合覆盖问题

假如你办了个广播节目。要让全美50个州的听众都收听到，为了支付较低的费用，你决定在尽可能少的广播台播出。
每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。


求完美解的时间复杂度O(2^n),会导致运行时间太长，不符合实际应用。
我们可以采用近似算法，贪婪算法解决。

衡量一种近似算法的好坏只要有两种标准：

  1. 运行速度；
  2. 得到的近似解与最优解的接近程度。

运用贪婪算法解决集合覆盖问题

假设有如下的州：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#传入一个州数组并转换为集合set，表示还需要覆盖州
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_covered   
  final_stations.add(best_station)  

 print final_stations

set:
集合的特点是去重，在前面的博文有提过用JS的Set对象，进行去重。我猜测JS应该借鉴了python吧。
集合运算：|（并集）,&（交集）, -（差集）
item():
Python 字典 items() 方法以列表返回可遍历的(键, 值) 元组数组。

NP完全问题

旅行商问题：游览n个城市（不重复），可能的路径有多少条？
答案是：n!。当要求精确求出最短路径时，就需遍历n!条路径（当n=10时，n!= 3 628 800）。可以看出，当n越大，路径就急速增加，所以求出精确解也是不符实际。所以，只能近似求解。
上述的旅行商问题和集合覆盖问题同属于NP完全问题，对于此类问题较为合适的方法是近似求解，而不是求完美解。
这样就诞生一个新的问题：什么问题才是NP完全问题？
NP完全问题特征：

  • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
  • 涉及“所有组合”的问题通常是NP完全问题。
  • 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
  • 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
  • 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
  • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

idea:

  • 贪婪算法与内存管理
  • 没点数学思维，快递我都送不好，快递小哥辛苦了！