日常生活中的算法

在日常生活中有时会碰到一些与算法有关的事情，现例举如下。

1) 最稳定婚姻

假设在婚介所有4对男士(A，B，C，D)和女士(a, b, c, d)，每人手中都有一张表，
上面有他(她)所喜欢的人(按最喜欢的，次最喜欢的等顺序列出)。如，男士A的表是
c b d a, 而女士c 的表是A C D B。当然，A-c 的结合是最稳定的婚姻，因为双方
都找到他(她)所喜欢的人。当人数较多时，我们得用算法找到最稳定婚姻。算法是
由男士建议他最喜欢的女士开始，如果该女士不反对(或她认为她的临时对象不如这
位男士)，这位男士就和这位女士结成临时一对。算法不断循环，最后找到所有的最
稳定婚姻。类似的问题还有毕业生分配到单位的问题等。

2) 企业转让

一般来说，生产企业的转让价格往往比企业资产的价格高。为什么？假设一企业有
两种产品，生产第一种产品每件需占用设备A 6小时，利润为1元；生产第二种产品
每件需占用设备A 2小时，占用设备B 5小时，利润为2元。设备都是24小时运行。设
两种产品的数量分别为X1和X2。对企业来说，是在约束条件下：5*X2 <= 24；6*X1 
+ 2*X2 <= 24；X1 > 0；X2> 0；达到最大利润Z: MAX Z = X1 + 2*X2。这是一个线
性规划问题。现有某企业要收买该企业。设Y1和Y2分别为单位时间设备A和设备B的
出让价格。要想该企业出让资源，出让价格产生的利润应不低于现有的利润：

6*Y1 >= 1； 2*Y1 + 5*Y2 >= 2。出让价格也被称为影子价格。

因此，如果企业赢利比较好，企业的转让价格往往比企业资产的市场价格高。

3) 削价大拍卖

商店为了占有更多的市场份额，常常用削价大拍卖来挤其他商店。由于其他商店也
跟着降价，结果是价格降了，利润少了，但占有的市场份额没有变。这是对策论(博
弈论)中的不合作非零和对策问题。经典的例子是“囚犯难题”。涉嫌一案件的两嫌
疑犯被分别拘留和监管。根据法律，如果两人都不承认此案是他们干的，则每人各
判一年；如果两人都承认，则每人各判八年；如果一人承认而另一人不承认，则承
认的人判三个月而不承认的人判十年。很明显，如果两人合作，都不承认此案是他
们干的，则得到比较好的结果(各判一年)。因为两人不可能合作，最后的结果是每
人各判八年。从理论上来说，这是不合作非零和对策问题的平衡状态解。回到削价
大拍卖问题，这问题与“囚犯难题”类似。由于削价大拍卖，两家商店的商品的价
格都降为2元，这是不合作的平衡状态解。如果两家商店合作将价格定为4元，两家
商店都能得到比较大的利润。如果一家商店将价格定为4元，而另一家商店违反协议
将价格定为2元，则前者得到很少的利润而后者得到很大的利润。现实世界上的对策
问题比这些要复杂得多，而且一些不合作非零和对策问题至今还没有完全解决。

4) 就餐问题

经典的例子是“五位哲学家就餐问题”。五位哲学家围坐一圆桌，每人面前有一盘
面条，每人左手侧和右手侧各有一叉子。吃面条时必须左手和右手各拿一叉子。如
果五位哲学家同时拿起左手侧的叉子，则谁也吃不成面条。这里有一个并行算法问
题。可以设计一程序，它能保证在任何时候有两位哲学家在吃面条。在现实世界上，
没有人是这样吃面条的，但是很多资源分配和并行算法问题都与这个问题类似。

5) 生日问题

参加一个大聚会人们往往会惊奇地发现有人和他的生日相同。一般来说，在一个23个
人的聚会就有50%的可能两个人有相同的生日。对一个人来说，某天是他的生日的概
率是1。对第二个人来说，某天不是他的生日的概率是364/365。所以两人生日不相
同的概率是：1*(364/365) = 0.9973。对三个人来说，三个人生日各不相同的概率
是：1*(364/365)*(363/365) = 0.9918。依此计算，我们可以得到，对23个人来说，
23个人生日各不相同的概率是：0.4927。因此我们就有上述结论。世界上有许多巧
合的事情，如有人在短时间内中了两次彩票等等。用概率论来分析，这种“巧合”
并不是巧合，它是概率相当大的事件。上述结果也被用于解密算法中。将待解密的
密文成对组合，然后进行解密，破译的可能性就大为增加。