第6章　处理困难的问题

在第2章，我们看到了P=NP的美好世界。生活将如此轻松，人们可以对一切进行最优化，了解万事万物。我们将拥有让人心想事成的机器。这一切太过美好了，以至于有点吓人，而且几乎肯定是不切实际的幻想。

我们更可能生活在一个相对混乱的世界，一个P≠NP的“不优雅”的世界。即使P=NP，在找到解决NP问题的算法之前，我们还是一样生活在P≠NP的世界。那么对于那些我们不能有效求解的问题，我们该怎么处理？直接放弃吗？

有时候我们不得不处理困难的问题。哈利在Acme制造厂担任主调度师。老板艾米让哈利安排机器的调度方案，来生产Acme最新的手机A-Phone，并要求使用的时间尽可能短。哈利读了本书开头的几章然后回答：“对不起，但那个问题是NP完全的。连很多著名的计算机科学家都不相信这类问题存在有效的解决方法，所以我试也是白试。我还是去打保龄球吧。”艾米直接祝哈利玩得开心，然后不用来上班了。

艾米很快提拔了乔治来代替哈利。幸好乔治读了本书的这一章，然后拟出了一个生产A-Phone的调度方案。乔治写出了一个总能找到最好的调度方案的美妙算法吗？没有。但是乔治有没有把事做完?是的。

NP完全问题是难以驯服的野兽，如果有P≠NP，那我们不可能找到一个能对所有问题总给出最好方案的快速算法。然而我们不必放弃，本章我们就来看看有哪些方法能在处理困难问题时派上用场。

对于中等规模的问题，我们可以用如今非常快的计算机遍历所有的解决方案。我们可以采用一些虽然不能包治百病，但对我们关心的问题起作用的算法。还有的算法虽然不能给出所有可能方案中最好的，但是能给出一个足够好的方案。

有的时候你想尽办法也找不到一个NP完全问题的解决方法。你可以试着解决一个不同的问题，或者干脆放弃。天涯何处无芳草，何必在一棵树上吊死。