贪心算法简记
一、概念
贪心算法的理念是每步都选择局部最优解，最终得到的全局最优解。
贪心算法的特点是实现起来很容易，运行速度快，得到的结果又与正确结果相当接近。
贪心算法可以认为是一种近似算法
二、一般步骤
（1） 选出当前最优
（2） 重复直到覆盖所有情况
三、近似算法
指能为问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值
在获得精确解（最优解）需要的时间太长时，可使用近似算法。
判断近似算法优劣的标准如下：
（1） 速度有多快；
（2） 得到的近似解与最优解的接近程度。
近似算法被认为是面临NP完全问题时的最佳做法
四、NP完全问题
1、定义
P 问题是指可以在多项式时间内求解的问题。
NP 表示不确定性多项式时间（nondeterministic polynomial time），NP 问题是指在多项式时间内近似验证答案的问题。但很多此类问题需要指数时间才能求解。
NP完全或NP完备 （NP-Complete，缩写为NP-C或NPC），是NP中最难的决定性问题，目前为止并未发现任何能在多项式时间内解决NP完全问题的方法，甚至认为根本不可能找出快速解决方案
2、典型例子
旅行商问题和集合覆盖问题是NP完全问题的典型例子
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。
3、NP完全问题的判定
没办法判断问题是不是NP完全问题，但NP完全问题往往有以下特征
（1） 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
（2） 涉及“所有组合”的问题通常是NP完全问题。
（3） 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
（4） 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
（5） 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
（6） 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。