1701018120
数学文化教程 [:1701013763]
1701018121
数学文化教程 第四节 算法复杂性：计算机的速度还太慢！
1701018122
1701018123
计算机的计算速度之快，远远超出了人们的想象，每秒运算一亿次的计算机已经十分平常。但是从解决数学问题的要求来看，有时还是嫌它太慢了。一亿次是108，一年约3.2×107秒，所以即使计算机不停地运行，一年也只能运算3.2×1015次。如果一个数学问题要计算30！次，而30！≈2.6×1032，这就是说，要计算机不停地计算8.1×1016年，这是难以接受的。因此，即使是计算机时代，计算的复杂性仍然是我们必须面对的数学问题。下面来看一个例子。
1701018124
1701018125
旅行售货员问题 假设有位投送货物的售货员，要选择投递路线：从商店出发，经过一组顾客中的每一位的住处一次，再返回商店，使得总行程最短。这就是有名的旅行售货员问题，简称TSP（travelling salesman problem）。因为这个问题又可以叙述为：一位售货员从n个城市中的某一个城市出发，到其他城市推销产品，要求每个城市到达一次且仅一次，再回到原出发城市；问如何选择旅行路线，使得总的行程最短？类似地，一些生产自动线的加工顺序问题也可以归结为这类问题。初看起来，这一问题似乎很容易解决：只要枚举可能的各种情况，从中选择最优的那一个就可以了。但是，随着n的增长，用枚举方法几乎是不可能的。
1701018126
1701018127
我们来看那位售货员的行走路线。如果他要走访20位顾客一次且仅一次，不同的路线可以如下产生。首先，第一站有20种选择。然后，第二站有19种选择，如此继续选择，可知最后给出的不同的路线会有20！种。由于某条由首站到末站的路线和由末站经历同样中间站再回到首站的路线实际上是同一条路线，所以要除以2，即
1701018128
1701018129
1701018130
1701018131
1701018132
1701018133
为了选取最短的路线，一个笨办法是将这些路线的长短两两作比较，因此一共要比较次，才能找出最短路线。由于这个算法太笨，以每秒进行1 000亿次运算的计算机求解，则需要4个半月。这样一个看似简单的问题，如果需要花费几个月甚至更多时间才能计算出结果，实际上是行不通的。
1701018134
1701018135
为了讨论方便起见，我们假定计算机的存贮量足够大，运算时间任意长，计算精度也足够保证问题的要求，这样“理想”的计算机称为图灵机（Turing Machine）。在图灵机上解题，计算时间的长短主要与以下因素有关：
1701018136
1701018137
（1）计算机的速度；
1701018138
1701018139
（2）实际问题规模的大小；
1701018140
1701018141
（3）算法的选择。
1701018142
1701018143
如果研究的问题，其规模n是确定的，此时解题所需的时间主要与计算机的速度和选择的算法有关。
1701018144
1701018145
以fA （D，n）表示用算法A求解规模为n的问题所需的运算次数。要缩短运算时间或在一定时间内能解更大规模的问题，其主要办法为：提高计算机的速度和改进算法，减少运算次数。
1701018146
1701018147
首先考虑前者的影响。如果现有的计算机每小时解题的规模为n，则用了快100倍、1 000倍的新计算机后，一小时所能解决问题的规模会如何变化？请看表8.4.1。
1701018148
1701018149
表8.4.1 计算机速度与解题规模之间的关系
1701018150
1701018151
1701018152
1701018153
1701018154
从上述表格中，可以看出：算法复杂性为规模n的多项式时，计算机成倍提速后，相应地解题规模也成倍增长；对算法复杂性为指数函数的算法，例如当f A （D，n）=3n时，计算机提速1 000倍后，解题规模n只能增加6.29。所以，对指数函数的算法，单纯靠计算机提速来增加解题的规模n，收效甚微。因此转向算法的研究是必要的。
1701018155
1701018156
首先对算法进行分类：如果存在多项式P（n）和正整数n0，使得当n＞n0时，恒有fA （D，n）＜P（n），则称A为解决问题D的多项式算法，又称为有效算法，或好算法。如果fA （D，n）是n的指数函数，则称算法A为解决问题D的指数型算法，又称为“坏”算法或“无效”算法。例如，求解旅行售货员问题就是指数型算法。
1701018157
1701018158
对于一个算法复杂性为n80的问题，虽然是多项式算法，但实际上也是不可接受的。因为280≈1024是一个“天文”数字，在现实情况下几乎不可能算出结果。幸运的是，一个实际问题一旦找到多项式算法，经过一系列的改进，其算法复杂性一般会降到n的三次多项式，甚至更低。因此有理由相信，多项式算法总是有效的。
1701018159
1701018160
我们定义的算法复杂性是考虑所有可能情况下，算法的运算次数。而实际上，有些算法只是在“最坏的情况”下才呈现指数型的增长，在一般情况下则很有效，因此仍然被人们广泛采用。例如，求解线性规划通常使用单纯形法，在一般情况下的平均运算次数是规模n的多项式，速度很快，但已经证明它在“罕见”的情况下是一个指数型的算法。
1701018161
1701018162
大多数的指数型算法，只是穷举搜索法的变种。只有对问题的结构充分了解后，才有可能给出多项式算法。解决实际问题时，当然要寻求多项式算法。但如果一个问题已经被证明没有多项式算法，再寻找精力就白费了，因此有必要对实际问题进行分类。
1701018163
1701018164
P问题和NP问题 对于一个实际问题，如果其存在多项式算法，则称为P问题（polynomial problem）。对P问题研究的中心问题是如何改进现有的计算方法使运算次数更少。如果已经证明不存在多项式算法，则我们认为这一个问题是难问题。对于难问题，一般只能寻找可以接受的近似算法。
1701018165
1701018166
还有一类实际问题，称为判定问题；是能用“是”（有）或“不”（无）来回答的问题。例如，问用2 500元能够购置29英寸的彩色电视机吗？回答这个问题“能”时，不必知道当前市场上29英寸彩电的最低价，只需了解确有价格不超过2 500元的29英寸彩电出售即可。对于一个判定问题，如果对所有回答为“是”的实例，都存在多项式算法来验证它的正确性，则称此判定问题为NP问题（不确定多项式问题，non-deterministic polynomial problem）。显然P问题一定是NP问题。
1701018167
1701018168
1971年，美国计算机科学家库克（Stephen Cook，1939—）发表了一篇十分著名的论文《The Complexity of Theorem-Proving，Association of Computing Machinery》。他首先指出，NP问题中存在一类称为NPC问题（完备问题，non-deterministic polynomial complete problem）。这类问题有如下特性：
1701018169