组合最优化与计算复杂性综述

摘要：综合论述了组合最优化理论与计算复杂性理论，尤其是NP-完备理论之间的密切关系，揭示出NP-完备理论研究的重大理论和现实意义。

关键词：组合最优化；计算复杂性；NP-完备；近似算法

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2013）13-3140-02

1 组合最优化

经典数学主要研究问题的存在性，唯一性和稳定性等，很少涉及组合最优化问题，一个主要原因就是人们不具备有效的数值计算能力。科学技术的发展使得组合最优化的重要性日益显现出来，而计算机的产生与发展则使得人们的计算能力大大增强，从而为解决组合最优化问题提供了可能；同时，在计算机的发展过程中，人们又提出了不少亟待解决的组合最优化问题。由此可见，组合最优化与计算机科学是相辅相成，紧密联系的。

2 计算复杂性

如上所述，组合最优化就是要找到适用于计算机的计算方法。这一方法应普遍适用于问题包含的所有实例（instance），求出实例的解。这样的计算方法就是算法。算法是计算机科学的核心概念，被誉为计算机科学的“灵魂”。算法的优劣直接关系到软件乃至整个计算机系统的性能.。著名的方正排版软件系统就是基于新的更有效的算法设计的。

那么，评价一个算法是否有效的标准是什么呢？一般而言，理论计算机科学界普遍以算法的计算复杂性，即算法在最坏情形（worst case）下的运行时间作为评价其有效与否的标准。然而，算法的运行时间与很多因素有关，如计算机的速度，问题的规模等。首先，我们假定算法是在“理想计算机”上运行的。理想计算机只能执行最基本的加、减、乘、除、大小比较等基本运算，且耗费的时间都是一个时间单位。因此，算法的运行时间常用算法所执行的基本运算的次数来表示。其次，一个待解决的问题的实例总是以一定的规模（size）输入计算机中的，如图和网络的顶点数和边数。因此，可设法估计出算法对规模为[n]的实例需执行的基本运算的次数的一个上界[f（n）]，将函数[f（n）]作为该算法的计算复杂性[1-3]。

显然，即使对于同一个问题的实例，不同的算法的计算复杂性也是不同的。以下面的旅行售货员问题[1]为例：有[n]个城市，任两城市之间都有路相通。一售货员拟从他所在的城市到其它[n-1]个城市去售货。问：这个售货员应如何选择路线，才能经过每个城市恰好一次，再回到原地，且总路程最短？

由数值计算理论知，当变量的个数增加时，多项式函数比指数函数增加的速度慢很多。基于这一事实，人们通常认为只有计算复杂性是多项式函数的（精确的）算法才是有效的算法。在上例中，由Stirling公式知，枚举法的计算复杂性是[n ！≈2nπ×（ne）n]，显然不是一个有效算法。

3 NP-完备理论

在NP类问题中有这样一些问题，如果其中有一个存在（不存在）有效算法，那么所有其它问题也都存在（不存在）有效算法，这些问题被称为NP-完备问题或NPC问题。绝大多数组合最优化问题都是NP-完备的。

NP问题的研究始于20世纪70年代。1971年，图灵奖得主Cook[4]证明了第一个NP-完备问题-适应性（satisfiability）问题。1972年，另一个图灵奖得主Karp[5]证明了24个NP-完备问题。到目前为止，大约有两千多个问题被证明是NP-完备的；然而，遗憾的是，人们尚未找到任何一个NP-完备问题的有效算法。但是鉴于NP-完备问题在理论和应用上的重要性，人们又不能回避它们。幸运的是，在很多实际应用中，人们只需找到NP-完备问题的“不错的”解，而不必是最优解。因而，近似算法成为求解NP-完备问题的方法之一。

4 结束语

生命科学和生物工程被称为当今科学技术的又一次革命。在这一伟大工程的研究过程中，许许多多包括NP-完备的组合最优化问题在内的困难问题被提出来，计算生物学（computational biology）或生物信息学（bioinformatics）也随之应运而生。近似算法技术在这一新兴学科的诸多研究领域都得到了成功地应用，如基因组的排序（genome sorting），进化树（phylogenetic tree）的构建，蛋白质结构的测定等。我们相信：伴随NP理论的深入研究和NP完备问题的最终解决，组合最优化的理论和方法必将为人类文明作出更大的贡献。

参考文献：

[1] 刘家壮，徐源.网络最优化[M].北京：高等教育出版社，1991.

[2] 顾小丰，孙世新，卢光辉.计算复杂性[M].北京：机械工业出版社，2005.

[3] 苏德富，钟诚.计算机算法与分析[M]. 2版.北京：电子工业出版社，2005

[4] S. A. Cook. The complexity of theorem proving procedures[J]. Proc. 3rd ACM Symp. On the Theory of Computing， ACM， 1971， 1514-158.

[5] R. M. Karp. On the complexity of combinatorial problems[J]. Networks， 1975， 45-68.

[6] N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem[R]. Technical Report， Graduate School of Industrial Administration， Carnegie-Melon University， Pittsburgh， PA 1976.

[7] L. G. Khachiyan. A polynomial algorithm in linear programming[J]. Soviet Math. Dokl.，1979，191-194.