首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》原则:如果没有显而易见的解法,将问题归约为另一个有解的问题

关灯直达底部

问题归约(Problem reduction)是计算机科学和数学中用于解决问题的一个基本方法。一个简单的例子,假如你需要一个算法来找到列表中的第四大的元素。不需要编写什么特殊的代码,你只需要用任何一种排序算法排个序,就能够在一个有序的列表中取到第四大的元素了。使用这个方法,你可以获得O(n log n)的性能。当然这并不是最高效的解决方法,看看第4章中我们讲到的selectKth,它才是最快的。

第8章所描述的问题看似有关联,却不太容易将它们联系在一起。其实可以将这些问题归约为线性编程(Linear Programming),并使用现成的商用软件包(比如Maple)来计算,然而归约过程太过复杂。其实通用算法完全可以来求解线性编程问题,尤其是Ford-Fulkerson算法族。

我们在第8章里已经展示了如何解决一类问题,这类问题称为网络流的最大流最小割。一旦这个算法在手,其他五个问题也就迎刃而解了。

表11-5展示了第8章谈到了网络流算法。