教室调度问题
场景
- 假设有五节课，从早上九点开始，每节课上一个小时，上到 12 点
- 如何将尽可能多的课程安排在同一个教室
解法
- 看起来很难，实际上很简单
- 找出结束最早的课，它就是这个教室里面上的第一节课
- 接下来，必须选择第一节课后开始的课。同样我们选择结束最早的课
- 重复上述步骤
- 所以贪婪算法就是每一步都采取最优解，最终得到的就是全局最优解
- 但是贪婪算法并不总是完美的，请看背包问题
背包问题
场景
- 假设你是个贪婪的小偷，背着可装 35 磅的背包，去商场偷东西
- 共三样，音响 300 美元 30 磅重，电脑 200 美元 20 磅重，吉他 150 美元 15 磅重
- 如果按照贪婪算法，那么第一步就装了个音响就不能继续了
NP 完全问题
需要计算所有的解，并从中选出最短的那个
- 还没有找到快速解决的方法，只能用近似算法
定义
- 以难解著称的问题
- 旅行商问题
- 集合覆盖
近似算法
- 因为旅行商问题，5 个城市就是 5 的阶乘，一旦城市数量多了，根本不可能快速解出来
- 于是有人就想到了近似算法
- 随便选择出发的城市，然后每次选择下次要去的城市的时候
- 都选择最近的那个
如何识别 NP 完全问题
场景
- 你正在为篮球队挑选队员，需要优秀的后卫，高高的前锋。。。
- 手里有一个名单，其中每个球员都符合某些要求
- 从这些名单里选出来
- 这就是一个集合覆盖的问题
- 可以使用近似算法
- 找出符合要求最多的
- 重复上面，直到满了
关键
- 不能将问题分解成小问题的
- 涉及所有组合的
- 如果问题可以转换成集合覆盖或者旅行商问题
- 想想旅行商问题和广度优先搜索的最短路径，后面是从 a 点到 b 点的，前者是经由指定点的就是 NP 完全问题