目标
1.学习如何处理不可能完成的任务：没有快速算法的问题（NP完全问题）。
2.学习识别NP完全问题，以免浪费时间寻找解决它们的快速算法。
3.学习近似算法，使用他们可快速找到NP完全问题的近似解。
4.学习贪婪策略——一种非常简单的问题解决策略。

教室调度问题

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。你设法让这些可都在这间教室上，但是有些课有冲突。你希望在这间教室尽可能多的上课。
image.png
贪婪算法可以让你简单的达到这个结果。
1）选出结束最早的课，它就是在这间教室上的第一节课。
2）选出第一节课结束后才开始的课。同样，你选择结束最早的课，这将是第二节课。
3）重复以上步骤。

贪婪算法的优点就是简单易行，每步都选择局部最优解，最终得到的就是全局最优解。并非在任何情况下都行之有效，但是它易于实现。

NP完全问题

旅行商问题：
有一位旅行商，他需要前往5个城市。
这位旅行商要前往这五个城市，同时需要保证旅程最短。为此，可考虑前往这五个城市的各种可能顺序。
对于每种顺序，都需要计算总旅程，在挑选出旅程最短的路线。5个城市有120种可能，6个则有720种，7个有5040种，这个问题的大O表达式是O(n!) 。
阶乘：贪婪算法 - 图2

每当多增加一个城市时，需要计算的可能就更多。因此，如果涉及的城市很多的多，根本无法找到正确的解。

NP完全问题定义：没有全局最优解的问题。

最少硬币找零问题

最少硬币找零是给出要找零的钱数，以及可以用硬币的额度数量，找出有多少种找零方法。
如：美国面额硬币有：1，5，10，25
我们给36美分的零钱，看能得怎样的结果？

  1. function MinCoinChange(coins){
  2.    let coins = coins;
  3.    let cache = {};
  4.    this.makeChange = function(amount){
  5.        let change = [], total = 0;
  6.        //从最大面额开始
  7.        for(let i = coins.length; i >= 0; i--){
  8.            let coin = coins[i];
  9.               //当前面额小于剩余需要零钱
  10.            while(total + coin <= amount){
  11.                change.push(coin);
  12.                total += coin;
  13.            }
  14.        }
  15.        return change;
  16.    }
  17. }
  18. //确定面额
  19. var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
  20. minCoinChange.makeChange(36);
  21. //一个25, 一个10, 一个1

近似算法

解决旅行商问题
1.选定出发城市
2.每次选择最近的要去的城市
3.重复以上步骤

近似不是最优解，怎么判断近似算法优劣：
1.速度有多快，贪婪算法大O表达式O(n)
2.得到的近似解于最优解的接近程度。

如何识别NP完全问题
没有办法判断问题是不是NP完全问题，但还是有一些规律的
元素较少时算法的运行速度非常快，但随着元素数量增加，速度会变慢。
涉及“所有组合”的问题通常是NP完全问题
不能将问题分成小问题，必须考虑所有可能的情况，可能是NP完全问题。
涉及序列且难以解决，可能是NP完全问题。
涉及集合且难以解决，可能是NP完全问题。
问题可以转换成集合问题和旅行商问题，肯定是NP完全问题。

小结

贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还么有找到快速解决方案。
面对NOP完全问题是，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。