日常生活中的算法

在日常生活中有時會碰到一些與算法有關的事情，現例舉如下。

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。因此我們就有上述結論。世界上有許多巧
合的事情，如有人在短時間內中了兩次彩票等等。用概率論來分析，這種“巧合”
並不是巧合，它是概率相當大的事件。上述結果也被用於解密算法中。將待解密的
密文成對組合，然後進行解密，破譯的可能性就大為增加。