 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 查看: 2193 | 回復(fù): 13 | ||||
gongtianyu鐵桿木蟲 (正式寫手)
|
[交流]
單身男女不用慌，死理性派讓你們成功速配
|
|
一些朋友喜歡看江蘇衛(wèi)視的《非誠勿擾》，不過在里面，四五個(gè)男生對(duì)二十四個(gè)姑娘，磨磨唧唧一個(gè)多小時(shí)，還常常配對(duì)失敗……死理性派表示：給我100 個(gè)男人100個(gè)女人，就可使其一一配對(duì)，還不會(huì)有人私奔。 聽起來很扯吧？然而數(shù)學(xué)家們可是切切實(shí)實(shí)地研究過這個(gè)問題哦。這就是所謂的穩(wěn)定匹配問題(Stable Marriage Problem，也叫穩(wěn)定婚姻問題）。 先對(duì)意中人排個(gè)名要進(jìn)行速配，當(dāng)然要考慮男女雙方的意愿。不幸的是，要讓每一個(gè)人都剛好能和自己最喜歡的人在一起基本上是不可能的（所以才有那么多三角戀多角戀�。偛幻庥腥俗罱K得不到自己最愛的那個(gè)TA，這時(shí)候他就不得不考慮“第一喜歡”的人、“第六喜歡”的人……所以，每個(gè)人都必須將對(duì)面的100個(gè)異性按最喜歡到最不喜歡排個(gè)序，不妨稱之為“偏愛序”。 然后就能按照所有人進(jìn)行速配了，而且這個(gè)速配是穩(wěn)定的，不會(huì)出現(xiàn)“私奔”的情況呢。 什么是不穩(wěn)定，有人曾用一句不太雅但很形象的話來描述：不穩(wěn)定婚姻意味著不但我家要有一枚奸夫，你家還要有一只淫婦才行。也就是說，A男喜歡B女勝過自己的妻子，同時(shí)B女喜歡A男勝過自己的丈夫，然后他們就私奔了。 在這場速配中，如果出現(xiàn)私奔，那它就是不穩(wěn)定婚姻，反之則為穩(wěn)定婚姻。 怎樣速配：Gale & Shapley 方法其實(shí)早在1962年，美國數(shù)學(xué)家戴維·戈?duì)枺―avid Gale）和勞埃德·夏普利（Lloyd Shapley）就解決了這個(gè)問題。他們的思路是這樣的： 第一天 上午，所有的男人都向自己最愛的女人求婚。 下午，每個(gè)女人清點(diǎn)自己的求婚列表。如果只收到一個(gè)男人的求婚，那么就和他訂婚。如果收到多于一個(gè)男人的求婚，那么就和其中她最愛的那個(gè)男人訂婚，同時(shí)把其他男人都拒絕掉。如果一個(gè)求婚都沒有，不要著急，最后總會(huì)有的。 晚上，檢查一遍，如果所有女人都訂婚了，那么，萬事大吉，第二天舉行集體婚禮。 但如果還有女人沒有訂婚，那么事情還沒完，第二天繼續(xù)。 第二天 上午，所有還沒訂婚的男人向自己次愛的女人求婚。（昨天他們已經(jīng)被最愛拒絕了） 下午，每個(gè)女人再看一遍自己收到訂婚的情況。如果她已經(jīng)訂婚了，但是又有一個(gè)她更愛的男人來向她求婚，那就把原來那個(gè)拒絕掉，再和這個(gè)更愛的男人訂婚；如果還沒訂婚，那就和第一天的下午的處理一樣。 晚上再檢查一遍，如果還是有人沒有訂婚，那第三天再重復(fù)。 第三天 上午，所有沒有訂婚的男人，包括第一天訂了第二天又被踹出來的，再向還沒有拒絕過他的女人中他最愛的那個(gè)求婚。 如此周而復(fù)始，直到最后大家都訂了婚，就舉行集體婚禮。 這是一個(gè)對(duì)男人有利的速配法直覺上，女性在這個(gè)匹配算法中貌似更有優(yōu)越感——男人們來向自己求婚，自己可以挑選一個(gè)自己最喜歡的。而男人們很可能會(huì)屢屢被拒。 那么這個(gè)算法是否真的是對(duì)女性比較有利呢？讓我們分別考察男人和女人如何才能得到自己的最喜歡的人。設(shè)A男要得到他最喜歡的B女，首先要看還有多少別的男人同時(shí)也喜歡B，然后再與這些情敵競爭。而女人是否能與最喜歡的男人結(jié)婚，首先就要看她自己在對(duì)方的偏愛序中排老幾，也就是說，一開始她就要和所有的同性競爭了。 在這個(gè)算法里，男人相比女人最大的優(yōu)勢(shì)就是他是主動(dòng)的一方，即使像櫻木花道一樣被拒了50次，仍然可以追求他喜歡的晴子。你也許會(huì)說，漂亮的女生肯定會(huì)有很多男人追啊。話是沒錯(cuò)，可是她心中的那個(gè)他不喜歡自己，那再多的追求者也枉然啊。 所以啊，姑娘們要想要好GG，還是得自己主動(dòng)啊。 附：Gale & Shapley 方法的合理性說明 算法的可終止性可證：每個(gè)男人按照自己的偏愛序一個(gè)個(gè)求婚下來，一定有一個(gè)女人會(huì)要他——試想一個(gè)男人被一百個(gè)女人拒絕掉了，那他的偏愛序中已經(jīng)沒有人可以求婚了，所以他得不到配對(duì)，對(duì)應(yīng)地對(duì)面也肯定有一個(gè)剩女，可是這個(gè)剩女曾經(jīng)拒絕過他呀，也就是說她有更好的追求者呀，她怎么可能成為剩女呢？ 算法的正確性也可證：假設(shè)有A男和B女私奔了。那么A在B的偏愛序中必然比B的丈夫靠前，按照算法，女人最后選擇的一定是所有向她求婚的男人中她最喜歡的，這就是說A沒有向B求過婚（要不然B選的就是他了）。然而，男人是按照自己的偏愛序依次求婚的，而A又喜歡B甚于自己的老婆，所以A又必然向B求過婚。推出矛盾，故不可能出現(xiàn)私奔。 |
回復(fù)此樓» 收錄本帖的淘帖專輯推薦
 生活小常識(shí) |
» 猜你喜歡
一志愿重慶大學(xué)085700資源與環(huán)境總分308求調(diào)劑
已經(jīng)有6人回復(fù)
-
268求調(diào)劑
已經(jīng)有7人回復(fù)
-
302求調(diào)劑
已經(jīng)有11人回復(fù)
-
306求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料學(xué)學(xué)碩080502 337求調(diào)劑-一志愿華中科技大學(xué)
已經(jīng)有4人回復(fù)
-
求調(diào)劑
已經(jīng)有6人回復(fù)
-
313求調(diào)劑
已經(jīng)有3人回復(fù)
-
南昌大學(xué)材料專碩311分求調(diào)劑
已經(jīng)有6人回復(fù)
-
316求調(diào)劑
已經(jīng)有6人回復(fù)
-
346求調(diào)劑[0856]
已經(jīng)有7人回復(fù)
★
小木蟲(沙發(fā)+1，金幣+0.5):恭喜搶個(gè)沙發(fā)，再給個(gè)紅包
小木蟲(沙發(fā)+1，金幣+0.5):恭喜搶個(gè)沙發(fā)，再給個(gè)紅包
 |
2樓2011-05-25 10:44:05
★
小木蟲(金幣+0.2):搶了個(gè)小板凳，給個(gè)紅包
小木蟲(金幣+0.2):搶了個(gè)小板凳，給個(gè)紅包
|
|
3樓2011-05-25 10:45:00
師大學(xué)子
鐵桿木蟲 (著名寫手)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 5573.8
- 散金: 340
- 紅花: 9
- 沙發(fā): 3
- 帖子: 2031
- 在線: 161.3小時(shí)
- 蟲號(hào): 1293506
- 注冊(cè): 2011-05-12
- 專業(yè): 數(shù)理邏輯和與計(jì)算機(jī)相關(guān)的
4樓2011-05-25 11:30:28
么有明白~ 5樓2011-05-25 11:48:22
tqhyeah
金蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 1434.4
- 帖子: 3
- 在線: 24.5小時(shí)
- 蟲號(hào): 254472
- 注冊(cè): 2006-05-27
- 性別: GG
- 專業(yè): 生物化工與食品化工
6樓2011-05-30 15:22:39
7樓2011-05-30 15:50:49
 |
8樓2011-05-30 16:36:47
aimonkey
金蟲 (正式寫手)
- 應(yīng)助: 11 (小學(xué)生)
- 金幣: 1246.9
- 散金: 83
- 紅花: 1
- 帖子: 888
- 在線: 275小時(shí)
- 蟲號(hào): 867933
- 注冊(cè): 2009-10-10
- 性別: GG
- 專業(yè): 應(yīng)用高分子化學(xué)與物理
9樓2011-06-02 19:06:36
tearain
銀蟲 (小有名氣)
我是豬頭！
- 應(yīng)助: 0 (幼兒園)
- 金幣: 5.3
- 散金: 960
- 帖子: 262
- 在線: 30.5小時(shí)
- 蟲號(hào): 423294
- 注冊(cè): 2007-07-21
- 性別: GG
- 專業(yè): 抗炎與免疫藥物藥理
10樓2011-06-02 22:15:26
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 gongtianyu 的主題更新
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 材料學(xué)學(xué)碩080502 337求調(diào)劑-一志愿華中科技大學(xué) +3 | 順順順mr 2026-03-18 | 4/200 |
|
|---|---|---|---|---|
|
|
[考研] 機(jī)械專碩299求調(diào)劑至材料 +3 | kkcoco25 2026-03-16 | 4/200 |
|
|
|
[考研] 一志愿中國石油大學(xué)（華東） 本科齊魯工業(yè)大學(xué) +3 | 石能偉 2026-03-17 | 3/150 |
|
|
[考研] 085700資源與環(huán)境308求調(diào)劑 +12 | 墨墨漠 2026-03-18 | 13/650 |
|
|
|
[考研] 274求調(diào)劑 +10 | S.H1 2026-03-18 | 10/500 |
|
|
|
[考研] 294求調(diào)劑材料與化工專碩 +15 | 陌の森林 2026-03-18 | 15/750 |
|
|
|
[考研] 308求調(diào)劑 +3 | 阿姐阿姐家啊 2026-03-18 | 3/150 |
|
|
|
[考研] 290求調(diào)劑 +7 | ^O^乜 2026-03-19 | 7/350 |
|
|
|
[考研] 一志愿北京化工大學(xué)0703化學(xué)318分，有科研經(jīng)歷，求調(diào)劑 +4 | 一瓶苯甲酸 2026-03-14 | 4/200 |
|
|
|
[考研] 260求調(diào)劑 +3 | 朱芷琳 2026-03-20 | 3/150 |
|
|
|
[考研] 086500 325 求調(diào)劑 +3 | 領(lǐng)帶小熊 2026-03-19 | 3/150 |
|
|
|
[考研] 廣西大學(xué)家禽遺傳育種課題組2026年碩士招生（接收計(jì)算機(jī)專業(yè)調(diào)劑） +3 | 123阿標(biāo) 2026-03-17 | 3/150 |
|
|
|
[考研] 08工學(xué)調(diào)劑 +5 | 用戶573181 2026-03-20 | 5/250 |
|
|
|
[考研] 085410人工智能專碩317求調(diào)劑（0854都可以） +4 | xbxudjdn 2026-03-18 | 4/200 |
|
|
|
[考研] 0703化學(xué)調(diào)劑 +10 | 妮妮ninicgb 2026-03-15 | 14/700 |
|
|
|
[考研] 312求調(diào)劑 +8 | 陌宸希 2026-03-16 | 9/450 |
|
|
|
[考研] 一志愿南京大學(xué)，080500材料科學(xué)與工程，調(diào)劑 +4 | Jy? 2026-03-16 | 4/200 |
|
|
|
[考研] 326求調(diào)劑 +3 | mlpqaz03 2026-03-15 | 3/150 |
|
|
|
[考研] 327求調(diào)劑 +6 | 拾光任染 2026-03-15 | 11/550 |
|
|
|
[考研] 26考研一志愿中國石油大學(xué)(華東)305分求調(diào)劑 +3 | 嘉年新程 2026-03-15 | 3/150 |
|