算法图解第8章——贪婪算法

没有快速解决方案，每步都采取最优的做法。

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

集合：

类似于列表，只是不能包含重复的元素。

let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2]);

并集：将集合合并；

let union = new Set([...a, ...b]);
// Set {1, 2, 3, 4}

交集：找出两个集合中都有的元素；

let intersect = new Set([...a].filter(x => b.has(x)));
// set {2, 3}

差集：从一个集合中剔除出现在另一个集合中的元素；

let difference = new Set([...a].filter(x => !b.has(x)));
// Set {1}

贪婪算法例子：

选择广播可以覆盖到所有的州需要的最少广播台

//州的集合
let statesNeeded=new Set(["vf","sd","sf","se","dt","tg"])

//广播台列表
let stations = {};
stations["kone"]=new Set(["vf","sd","sf"])
stations["ktwo"]=new Set(["sd","se","dt"])
stations["kthree"]=new Set(["sd","sf","se","dt"])
stations["kfour"]=new Set(["se","dt","tg"])

//最终输出结果
let finalStations = new Set();

//计算
while (statesNeeded.size>0){
  let bestStation;
  let statesCovered = new Set();
  for (let station in stations) {
    //获取每个广播台范围的交集
    let covered = new Set([...stations[station]].filter(x => statesNeeded.has(x)));
    if(covered.size > statesCovered.size){
      bestStation = station
      statesCovered = covered
    }
  }
  //去掉已覆盖的州
  statesNeeded = new Set([...statesNeeded].filter(x => !statesCovered.has(x)));
  //添加选中的广播台
  finalStations.add(bestStation)
}

console.log(finalStations);
//Set { 'kthree', 'kone', 'kfour' }

NP 完全问题

以难题著称的问题，如旅行商问题和集合问题。简单来说，不可能编写出快速解决这些问题的算法。

判断 NP 完全问题的方法：

元素少时运行很快，元素数量的增加，速度会变得特别慢；

涉及“所有组合”的问题。通常是；

不能将问题分成小问题，必须考虑各种可能的情况。可能是；

问题涉及序列且难以解决，可能是；

问题涉及集合且难以解决，可能是；

问题可转换为集合覆盖问题或旅行商问题，肯定是。

NP 完全问题，没有快速解决方案，最佳的做法是使用近似算法，贪婪算法是不错的近似算法。