Day 27：碰到困难问题，演算法也救不了？

上一回我们说旅行推销员问题(TSP)是一个NP困难问题，没有快速的演算法可以解决。

那一个问题怎样叫做「困难」，演算法又要多快才叫做快呢？

如果说所有运算问题有容易与困难之分，NP困难的理论用明确的方式作出分野。不深入NP困难的定义、用最最简单粗浅的方式来说，容易是指可以以多项式时间的演算法解决，困难是指最坏情况需要指数时间。

我们之前讨论过的诸多演算法，如二分搜寻、快速排序...执行时间有O(n)，O(log n)、O(n²)、O(n log n)等等。虽然这些执行时间各有不同，n的大小也会依实际问题有所变化，但它们的共通点是都是n的多项式倍数，或者说可以表示为O(n^c)，其中c为一常数。这样的演算法可以被称为快速，而能以快速演算法正确解决的问题可以想为是容易的问题。

TSP被认为是困难问题，除了目前没有快速演算法可以解决，我们甚至还无法证明这样的快速演算法究竟是 1.存在但尚未找到，还是2.根本不存在，虽然多数科学家更倾向主张第二种情况[注1]。既无从证明快速演算法存不存在，当我们说一个问题困难时，并不是「绝对没有快速解」的意思，它比较像一种相对的表达，指这个问题至少与其他许多还没有快速解的困难问题一样困难。

分辨困难问题

其实现实生活中碰到困难问题的机率并不低，那我们怎麽分辨一个问题是否困难，进而调整策略呢？

一种方法是先熟悉一些已知是困难的问题，碰到新问题时，可以察觉出它们是同一类型问题。例如假设碰到的新问题是要以一个顺序解决一系列任务，而且每个任务的成本都跟前一个任务相关，那麽很有可能这其实是个TSP类型的问题，只是问题的描述或对象不同。

另一种方法是运用归约(reduction)的技巧，进行问题之间的转换，例如将一个困难的问题化为新问题，可以知道新的问题也是困难的。

应对困难问题

当在现实生活中遇到困难问题，使用已知的快速演算法硬解很有可能是徒劳的，这时候该怎麽办呢？除非刚好问题规模很小，可以直接解决，不然通常会需在在几个方面作出取舍。

1. 可能必须为个别问题设计出适用的演算法。例如利用动态规划解背包问题的例子，即是找到解决特定问题的子问题的方式。
2. 放弃百分之百的正确性，例如使用贪婪演算法，得到可接受的近似解，并节省很多时间。
3. 如果必须追求正确解，只能尽可能地缩短执行时间。也就是虽然没有快速演算法可用，至少尽量避免暴力解决法这类最慢的方式，像是利用动态规划解决TSP就是一个例子。

[注1]有兴趣想要了解这个难题可以参考P/NP问题。