[Kawaii的數學]
拍拖模型匹配
[由於內容較多無法一次寫完，本帖在完成前不斷更新。。]
phoeagon
首先，說一下拍拖模型。 [感謝_gXX提出本概念]
在這個模型中，有a個girl和b個boy。我們的拍拖只搭配男女之間，不考慮其他的情況。那麼，如果某個girl和某個girl是否有潛在的拍拖情緣，就在boy和girl之間用鉛筆連一條線[邊]。
如果他們間確定拍拖關係，就用蠟筆，用鮮豔的顏色把邊加深。而且，我們假設這些boy和girl都很好很innocent，都是一一對應的拍拖關係。顯然對於給定的一些boy和girl的潛在拍拖和正在拍拖關係可以用這樣的圖畫來表示。為了容易看【這不是絕對的要求】，我們讓女孩子站在在右邊，男孩在左邊。這個圖有boy和girl兩種節點，成為“二分圖”[拍拖關係圖]。
♂1 ♀1♂2 ♀2
女孩子站在在右邊，男孩在左邊。請你站在中間。
我的意思是說，作為一個安排拍拖的人，你應該理性思維為先，不要被愛意衝昏頭腦；所以請站在第三者，我是說，第三方，的角度冷靜客觀的看。
在正式進入之前，我們來看幾個和大家生活息息相關的問題。
1、在一個給定的拍拖關係圖中，讓一些有潛在拍拖情緣的boy和girl進行拍拖，令總體的戀人對數最多。
2、給每一對有潛在拍拖情緣的拍拖關係定義一個“幸福指數”，要求最後匹配的結果的幸福指數的和最大。
3、假設有n個boy和n個girl，每個boy和girl分別給另外n個異性的好感度做了排行[排行不得並列]，要求一個穩定的拍拖。 再這個問題裏任意一對boy和girl可以拍拖。
任意一對boy和girl沒有成為戀人，但是他們之間的好感度都比對自己拍拖物件的好感度高，那麼拍拖是不穩定的；因為他們可能為了自己的利益聯合私奔。[《組合數學》第三版]
//本節所有問題可以用單純形法求解線性規劃解決，如果您是這方面的牛請忽略此文。
第一個問題，是二分圖拍拖圖模型最基本的問題，成為最大拍拖匹配。
基本演算法圖：（下圖描述了一個一半的匹配結果和接下來的匹配步驟）
注意看上面的圖，看看程式如何增加一對匹配。
a、對於每個男生，隨便找可以拍拖的女生【二者有情緣且女生未拍拖】。
b、每次從男生出發，尋找一條沒有拍拖的潛在情緣，連接到一個女生，女生再找一條正在拍拖的情緣線連接到某個男生。最後形成：“沒有拍拖的關係－拍拖的關係－沒有拍拖的關係”類似的奇數條拍拖關係。改變這些關係，讓原來不拍拖的男女去拍拖，拍拖的就吹啦，這樣就可以增加一對戀人。
c、反復進行步驟二，直到找不到可以增加的交替拍拖關係鏈。輸出結果。
這個演算法成為最大匹配的匈牙利演算法。 當然這個問題可以用O(n)的時間轉化為單位容量的網路流問題，然後用FF（Ford Fulkerson）用O(mv)的時間求解，或者SAP（MPLA）到O(mn^2)；或者綜合二者做到O(min(n^(2/3)*m, m^(3/2)))。
2、這個問題成為匹配的最優匹配演算法。可以用費用流求解，具體步驟較為wS，不屬於本文討論範圍。
3、真正的主角出場，我們最重要的時研究一下穩定的拍拖模型。【SMP】
因為本文不是論文，只是從簡單的生活的角度探討一下拍拖模型，所以下面許多結論以不加證明的形式給出。
a、可以證明，當男女生數目相等時，這樣的穩定拍拖模型總是存在的，否則不一定存在。
b、定義：當n對boy和girl組成n對戀人時成為完備拍拖。 顯然對任意的n對boy和girl有總共n!種完備拍拖方案。 完備的拍拖才可能是穩定的。
c、演算法：
延遲認可演算法（Gale-Shapley演算法）
先對所有girl進行落選標記
當存在落選girl時，進行以下操作
1）每一位落選girl在所有尚未拒絕她的boy中選擇一位被他排名最優先的boy
2）每一位boy在所有已經選擇他，並且他尚未拒絕的girl中挑選被他排名最優先的girl，對她推遲決定，並于此時拒絕其餘girls。
於是，在演算法執行期間，由girl向boy申請拍拖，一些boy和girl拍拖。但是，如果收到更好的拍拖，boy可以取消。
因為根據定理a，一定存在一個拍拖狀態滿足要求。每個女士不可能被拒絕大於n次，所以演算法一定可以在有限步數內結束。
所以……
－－－－－－－－－－－－－－－－－－－－－－－－－
phoeagon先生：
請問憑什麼您讓女孩申請拍拖？這不公平。
××
－－－－－－－－－－－－－－－－－－－－－－－－－
好吧，可以這樣子來解釋一下。讓girl申請拍拖表面上似乎是對girl不利∼但是∼我們看，如果把演算法倒過來，顯然還是可以完成的∼這時∼
我們引進一個概念：
d、“女生最优－稳定拍拖”——在这样的方案中，女生获得的man总是在所有的“稳定拍拖方案”中可能得到的boyfriend中她最喜爱的。“男生最优－稳定拍拖”反之，对男士最有利。
在这个意义下，可以证明，让女孩子在 延迟认可 （Gale Shapley）算法 中主动申请拍拖可以为她们争取到稳定的拍拖中最最喜爱man，即得到一个“女生最优－稳定拍拖”方案。反之如果让男生主动的话会得到一个“男生最优”的方案。 同时不难证明，不主动方会的到最坏结果。就说，这个拍拖模型总是对一方极端有利对另一方反之的。当然，这也意味着，不主动的很可能被某个自己很不喜欢的对象追到，然后因为别人都拍拖了自己不得不拍拖的情况。
明白了吗？
------------------------------------
2 phoeagon：
现在好多了
××
------------------------------------
很显然，对于稳定拍拖还有一些很浅显的结论，例如：
e、如果有一对boy和girl，他们各自对对方的喜爱度都是排序中最高的，那么这对金鸳鸯一定要保存。（不难证明）
| 
