1701018109
1701018110
1701018111
表中各种对策组合出现的4种可能性都相同，概率都等于0.25。由表中数据，齐威王的收益为0和2的概率都是0.5。于是齐威王的平均收益为
1701018112
1701018113
0×0.5+2×0.5=1.
1701018114
1701018115
即齐威王和田忌若按随机对策方法赛上下两匹马，则齐威王平均每次赢田忌一千斤铜。
1701018116
1701018117
1701018118
1701018119
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的三次多项式，甚至更低。因此有理由相信，多项式算法总是有效的。