Day 22：贪婪演算法(2)

上一回写到大部分贪婪演算法并非永远正确，那哪些问题适合用它来解呢？

贪婪演算法既是在过程中不断地寻求局部最佳解，换句话说，它也就适合解决有办法透过局部最佳解推得整体最佳解的问题，或者称为拥有最佳子结构(optimal substructure)的问题。

举例来说，如果从A地到达C地的最短路径会经过B地，那麽其中A到B和B到C的路，应该也都是各自之间的最短路径，可以说A-B-C这条最短路径是由A-B和B-C的最短路径组成。

可是如果今天要找到最便宜的机票，从A地到C地最便宜的机票可能在B地转机，可是不代表买A到B最便宜的机票，再买B到C最便宜的机票会得到一样的结果，因为转乘的机票未必会等於两张单程机票钱加总。这里可能就无法用局部最佳解得到整体最佳解。

看到这些路径问题，可能觉得跟之前提到的Dijkstra演算法似曾相识。Dijkstra演算法确实就是运用了贪婪演算法的手法，透过每一次选择最短的路径，来找到整体的最短路径。

因此，如果一个问题的子问题最佳解可以组成整个问题的最佳解，那麽这个问题可能就适合用贪婪演算法解决。

另外一个运用贪婪演算法的时机是面对特别困难问题的时候。现实中的很多问题其实并不像设计过的演算法例题，可以用一两个演算法就快速又正确地解决。有很多问题是属於「困难」，必须花多到难以想像的资源(时间、空间)才有办法解决，也就是追求正确解是很不且实际的。

这时候可能就需要仰赖近似演算法(approximation algorithm)，这类演算法虽然未必能得到最佳解，但是能以合理的成本得到可以接受的近似解。而通常容易建构、执行速度快的贪婪演算法就可以是用来设计近似演算法的一种方式。

也可以说，在问题极其困难或不一定要绝对精确答案的时候，简单、快速、能得到近似解的贪婪演算法也可以是不错的选项。