1701018090
为了把齐威王与田忌赛马的故事引申成一个对策问题，我们先把双方出三匹马简化成各出两匹马，分别称为上马、下马。问题的假设如下：
1701018091
1701018092
（1）该对策问题中有两方，即齐威王和田忌，齐威王的上、下马分别优于田忌的上、下马；
1701018093
1701018094
（2）双方可选择的对策是己方马匹的出场次序，由于两匹马的排列次序共有2种，因此每一方各有2种可选择的对策；
1701018095
1701018096
（3）双方都预先知道对方所有可能的对策，并且预先知道双方每一种对策组合的结果；
1701018097
1701018098
（4）在比赛之前双方都不能预先知道对方究竟会采取什么对策，双方同时选择对策，没有先后次序关系，而且一场比赛的对策一旦选定就不允许变更；
1701018099
1701018100
（5）把赢铜一千斤记收益为“1”，输铜一千斤记收益为“-1”，则对策的一方齐威王在各种对策组合下的收益如下表所示：
1701018101
1701018102
表中的数字是在比赛双方采取相应对策时齐威王的收益。齐威王的收益就是田忌的损失，因而把表中的数字全部改变符号后就可以得到田忌的收益。那么在这个对策问题中齐威王和田忌应该怎样选择自己的对策，而最终的结果又会是怎样的呢？为了回答这些问题，我们先来看看问题有什么特点。
1701018103
1701018104
首先，由前面的分析可知，双方都不能让对方知道或猜中自己的对策，因为一旦自己的对策被对方知道，则对方就可以有针对性地采取适当的对策，自己就处于不利的地位。这也意味着任何一方的选择不能一成不变，对策的变动要使得对方无法预测为好。这就意味着选择对策必须要有一定的随机性。其次，无论对齐威王还是对田忌，两种可选择的对策相互之间没有优劣之分。如对齐威王来讲，每一种对策都可能有两种可能的结果，包括一种收益为2，一种收益为0。实际究竟得到哪种结果，要看双方对策的组合情况，而不仅取决某一方的对策。同样，对于田忌来说，他的两种对策也无好坏之分，每种对策也有两个可能的结果，可能的收益为0或-2。总之，比赛双方在选取对策时，对己方的可选对策并无偏爱，应以相同的可能性选用。实际上，偏向于某种对策的结果往往对自己不利，因为当对方得知你的偏爱后就可以针对性选择对策，从而有更多的机会取得有利的结果。这种对策游戏如果只进行一次，则双方的选择和最终的结果都无法确定，只能完全靠运气。由于齐威王的马的实力比田忌的马略高，他赢的机会比田忌要大得多。如果这样的对策游戏重复进行多次，则上面的讨论给我们指出了各方选择对策的原则，而且进一步讨论还能告诉我们多次比赛后的平均结果。这种对策问题称为随机对策问题，我们可以应用平均数来作计算。计算的方法如下。
1701018105
1701018106
齐威王的收益表
1701018107
1701018108
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）实际问题规模的大小；