正文

日常生活中的算法

(2022-09-25 13:37:58) 下一個

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

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

 

[ 打印 ]
閱讀 ()評論 (0)
評論
目前還沒有任何評論
登錄後才可評論.