贪婪算法 | Dong

简介

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

换句话说：贪婪算法就是每步都选择局部最优解，最终得到的就是全局最优解

贪心算法也存在如下问题：

不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑
贪心算法一般用来解决求最大或最小解
贪心算法只能确定某些问题的可行性范围

例子

教室调度问题

集合覆盖问题（广播站问题）

这一节的算法代码会在后面放出来，我们先专注于这个算法以及其应用先，毕竟会用但不知道在哪用就跟不会用差不多嘛

通过上面两个例子，我们可以得出如简介一样的总结，贪婪算法不算最优解，但是在某些复杂的问题下我们用它可以达到非常接近最优解的解，那什么又是复杂的问题，也就是哪些问题才需要用到贪婪算法呢

NP完全问题

NP完全问题的简单定义：以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。

比如旅行商问题，这个链接会讲述TSP问题以及帮你引入到贪婪算法里，懂了这一节的例子也可以不用看了

比如有这么三个城市-北京、石家庄、呼和浩特，你都想去旅游，于是有一天，你开始规划路线，那么从哪里出发，最后去哪里，你会如何规划呢

我们先不考虑起点从哪，假设我们想先去石家庄，然后去呼和浩特，最后再到北京，这便是其中一条路线，但我们想找出最短的那条路程，比较把时间花在路上，玩的很累不是吗，那么怎么选呢，穷举法？好像很不错的样子，我们来试试

北京-石家庄-呼和浩特

北京-呼和浩特-石家庄

石家庄-北京-呼和浩特

石家庄-呼和浩特-北京

呼和浩特-北京-石家庄

呼和浩特-石家庄-北京

然后就是在里面挑出一条最佳路线，显然，这个方法的时间复杂度是O(n！)

这可是阶乘啊，意味着啥，当你越来越富，想玩的地方越来越多，你要挑选出一条最佳路线的难度可是越来越大，原来有钱人也不是那么好的

那么这个时候我们就要选择贪婪算法了

如何识别 NP 完全问题

NP完全问题无处不在！如果能够判断出要解决的问题属于NP完全问题就好了，这样就不用去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小

下面几点可作为辨别NP问题的参考

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

练习

有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？
在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？
你要制作中国地图，需要用不同的颜色标出相邻的省。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻省的颜色都不同。请问这是NP完全问题吗？

代码实现

说完上面，我们来看看JavaScript如何实现广播站问题的贪婪算法

首先，运行该算法我们需要什么样的数据格式，一个用于存储省名的数组、一个用于表达广播站及其可以广播的省份的映射关系-散列表，在里面，我们用字母来表示广播站

//省份缩写
let address = ['GD', 'HN', 'AH', 'ZJ', 'HN', 'HB', 'FJ', 'GC', 'JS', 'SC'];

//广播站-散列表
let radioStation = {
  a: ['GD', 'HN', 'AH'],
  b: ['AH', 'ZJ', 'HN', 'SC'],
  c: ['HN', 'AH', 'ZJ'],
  d: ['FJ', 'GC', 'JS'],
  e: ['HN', 'HB', 'FJ', 'GC', 'JS'],
  f: ['HN', 'HB', 'FJ', 'SC'],
};

接着就是算法的实现了

记住我们的步骤

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

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

根据第二步，我们就应该会感觉到可能要用到迭代了

首先先不管用不用迭代，我们来分析下这个过程

最核心的一步：我们要找出最多的未覆盖省份的广播站，那么这一步如何实现

通过遍历广播站，找出广播站和所需要覆盖的省份间的交集，谁的交集包含的元素最多，就选哪个，这就是最核心的了，遍历、交集、最多，这三个名称就是算法核心代码了，如下

// 最大地址数的广播站所能广播的地址
let maxAddressStation = new Set();
// 最大地址数的广播站名称
let station = Object.keys(radioStation)[0];

// 遍历radioStation，将每一项与addressCollection进行交集
for (const key in radioStation) {
  const element = radioStation[key];
  let intersection = new Set(address.filter(i => new Set(element).has(i))); //取交集
  // 判断：若当前集合大于之前的集合，则重新赋值最大值
  intersection.size > maxAddressStation.size && ((maxAddressStation = intersection), (station = key));
}

接着遍历完第一遍，有可能会剩下其他省份还没找出广播站呢，那该如何做呢，再对剩下的省份执行上述步骤嘛，这不就要用到迭代了，代码如下，我们用res这个变量用于存储最终的广播站结果集合，然后记得把当前选到的广播站从下次执行的函数参数中的数据删除

res.push(station); //将广播站压入
address = address.filter(i => !maxAddressStation.has(i)); //取差集，即剩下需要广播的地址
delete radioStation[station]; //排除当前已选择的广播站
return greedy(address, radioStation, res); //继续下次递归

既然是迭代，那肯定要有终止条件，不然就无限迭代下去了，这个问题的基线条件是所有的地址都已找到所能广播的广播站了，换成代码的解释就是address长度为零

// 基线条件（递归终止条件）
if (address.length == 0) {
  return res;
}

好了，这就是这个算法的大致代码了，等等，如果有一个地址没有任何广播站能广播到呢，出现这种情况怎么办，这种问题我们只能当作无解，毕竟没有广播站能广播到你要的地址，说明数据有问题，需求也就根本无法解决

代码上也就是，两者交集没有任何结果，如果address长度还没为0时，没有结果意味着没有广播站可以服务该地址了，所以注意该代码位置

1	if (maxAddressStation.size == 0) return '所选数据无解';

全部代码

// 贪婪算法： 参数：所有地点（数组）、广播站（散列表）、最终结果
function greedy(address, radioStation, res = []) {
  // 最大地址数的广播站所能广播的地址
  let maxAddressStation = new Set();
  // 最大地址数的广播站名称
  let station = Object.keys(radioStation)[0];

  // 基线条件（递归终止条件）
  if (address.length == 0) {
    return res;
  }

  // 遍历radioStation，将每一项与addressCollection进行交集
  for (const key in radioStation) {
    const element = radioStation[key];
    let intersection = new Set(address.filter(i => new Set(element).has(i))); //取交集
    // 判断：若当前集合大于之前的集合，则重新赋值最大值
    intersection.size > maxAddressStation.size && ((maxAddressStation = intersection), (station = key));
  }

  if (maxAddressStation.size == 0) return '所选数据无解';

  res.push(station); //将广播站压入
  address = address.filter(i => !maxAddressStation.has(i)); //取差集，即剩下需要广播的地址
  delete radioStation[station]; //排除当前已选择的广播站
  return greedy(address, radioStation, res); //继续下次递归
}