算法图解-贪婪算法

1. 贪婪算法很简单：每步都采取最优的做法。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。

2. NP完全问题
所有的非确定性多项式时间可解的判定问题构成NP类问题

• 世界七大数学难题之一
  美国麻州的[克雷]（Clay）数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元。

  “千僖难题”之一：P （确定性多项式算法）对NP （非确定性多项式算法）

  “千僖难题”之二：霍奇（Hodge）猜想

  “千僖难题”之三：庞加莱（Poincare）猜想

  “千僖难题”之四：黎曼（Riemann）假设

  “千僖难题”之五：杨－米尔斯（Yang-Mills）存在性和质量缺口

  “千僖难题”之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性

  “千僖难题”之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton-Dyer）猜想

NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。

3.如何识别NP问题

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

4.小结

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