什么是近似算法

先把完美放一放

有一道难题。要找完美的答案，就得把所有情况都考虑一遍，而情况多得吓人。
一直算到底，当然能得到最好的答案。可那要算到什么时候？
点一点，自己数数看。

把完美答案一直追到底会怎样。（情况数膨胀，时间爆炸 → 看不到尽头）

数量涨得太快了。只多几个，要考虑的就多出好几倍。
所以一直等到完美的答案，有时并不现实。可也不能因此就撒手不管。

足够好的答案，要快

这里有个想法：如果不一定非要最好的呢？
不去追求完美，而是干脆快速地挑出一个“还算不错的答案”，就像贪心那样，把眼前好的一个个麻利地选下来。

快速的估计答案 vs 完美的答案。（估计答案一眨眼就出来 · 差距不大）

估计答案一眨眼就出来了，和完美的答案却差不了多少。
虽然差一点，但够用。很多时候，这样就足够了。

保证有多好

不过还有一个担心：“还算不错的答案”这话能信吗？万一是个很糟的答案怎么办？
所以聪明的办法会附上一个承诺：“这个答案不会比最好的差太多。”

保证在最优的 1.5 倍以内。（不管得出什么答案，都在这条线内 → 最坏的情况被挡住了）

这正是了不起的地方。像“在最优的 1.5 倍以内”这样画好一条线，答案再差也越不过它。
虽然不完美，但它最多能差多少，我们清清楚楚。这和模糊的猜测完全不同。

拿准确度换时间

说到底，这是一杆秤。多花时间，答案更准；省下时间，答案就粗糙一点。
哪边更好，没法一刀切：赶时间就选快的，要求精密就选准的。
用按钮加减时间，在两者之间选一个位置。

多花时间更准，少花时间更粗。（在哪里停，由我们来选）

这杆秤，是贯穿整个算法的心思：快的路和准的路，简单的路和细致的路。
我们每一次都在选择付出什么、得到什么。懂得好办法，就是会读这杆秤。

一路走来

我们走了很长的路。从按顺序解题开始，排队、查找、量成本、拆分、连接、挑选。
也看到了有些问题真的很难，以及即便如此，仍有足够好的答案。
点一点，把这一路一下子回顾一遍。

按顺序整理这个领域教给我们的四件事。（好办法 · 快慢 · 策略 · 知道极限再折中）

不是每个问题都能完美地解决，但这并不意味着我们无能为力。
用快的办法和聪明的策略，知道极限、明智地折中，即使面对难题，也能拿到够用的答案。
这就是算法带给我们的力量。