# 演算法_王紹睿 ## Stable Matching ### Introduction 男女各有 $n$ 個人，並且每一個人會有一個異性喜好程度的表 ![](https://i.imgur.com/kgevAfP.png) 而我們要找到一種 stable 的配對方式（男對女） stable: 不會出現男女互相喜歡對方更勝於配對結果 以下就**不是一個 stable** 的配對 綠色代表配對的結果，黃色的格子代表還有更好的配對方式 （因為男生有更喜歡的女生，且那個女生也更喜歡新的男生） ![](https://i.imgur.com/q6ZNmGz.png) ### Solution ```cpp= # Gale-Shapley initialize each person to be free while (some man m is free and hasn't proposed to every woman) do w = highest ranked woman in m's list to whom m has not yet proposed if (w is free) then (m, w) become engaged else if (w prefers m to her fiance m') then (m, w) become engaged m' become free return the set S of engaged pairs ``` 每個人都會有三個狀態 - free 單身 - engaged 訂婚，這個時候是可以悔婚的 - married 結婚 迭代的中止條件是，沒有男生是 free 的 而在迭代中，男生會依照喜好程度表去找還沒有求婚過的女生（由高到低） 女生被求婚時可以分成兩個情況 - 女生是 free 的 無條件接受 男女雙方都進入 engaged - 女生是 engaged 的 依照自己的喜好程度表，判斷要不要悔婚（跟新的男生在一起） 這時候又會有兩種情況 - 女生悔婚了（跟新的男生在一起） 原本跟女生訂婚的男生變成 free 的 - 女生並沒有接受新的男生 新的男生求婚失敗，狀態還是 free ### Property - Termination: 至少在 $n^2$ 之後會停止迭代。 - Perfection: 每個人最終都有配對到對象。 - Stability: 由於是雙方自己選擇的，最終都會是 stable。 - Male-optimal and female-pessimal: 男生為最佳的結果，女生較為被動。 ### Proof #### Termination 這個演算法會中止 ```cpp w = highest ranked woman in m's list to whom m has not yet proposed ``` 從這一行來看，可以得知每一次求婚都會產生一組配對 - 如果女生是 free 的 則無條件接受男生的求婚，增加一組配對 - 如果女生是 engaged 的 不論是拒絕還是接受（悔婚），總配對數都不變 所以一定可以在 $n^2$ 之後停止迭代 #### Perfection 每一個人都會被配對 這邊用的是反證法，假設有一個男生是 free 的 再來看看迭代的中止條件 ```cpp while (some man m is free and hasn't proposed to every woman) do ``` 前面的 some man m is free 成立，如果要跳出迴圈的話 就表示後面的 hasn't proposed to every woman 要不成立 意思就是說，**這個男生已經跟所有女生求過婚了** 而根據題目所說的，男女各有 $n$ 個人 如果一個男生是 free 的，則也會有一個女生是 free 的 如果這個女生是 free 的，**就代表她沒有被任何人求過婚** **發生矛盾**，所以我們假設的前提不成立（假設有一個男生是 free 的） 因此我們可以說，每一個人都會被配對到 #### Stability #### Male-optimal and Femal-pessimal #### Tips ::: info 在證明演算法的特性時，證明特性的先後順序會影響難易度。 可以透過已經證明出來的特性，去推導比較難證明的特性。 ::: ### Application 這個配對問題可以應用在很多不同的場合 只要是有符合題目的一些條件，就可以使用 （有喜好程度表，並且沒有同樣喜好度的項） - 學生選學校 - 送往醫院的病人 - 室友配對 ## Interval Scheduling 區間排程問題 有數個任務，每個任務都有執行時間 而在同一時間內只能執行一個任務 求最多可以執行多少任務 ### Weighted Interval Scheduling 有權重的區間排程問題 每一個任務都會有權重 要求的是最大的權重，而不單看數量而已 ## Bipartite Matching （弱化版的 stable matching） 給一個 Bipartite Graph 要求最多的配對 ## Independent Set 給一個 Graph 找最多的 independent vertex ## Competitive Facility Location 給一個 Graph，每個節點都有權重 而現在有 $n$ 個玩家，這 $n$ 個玩家輪流選擇節點， 節點上的權重代表得分數，而每個玩家都要使自己的收益最大化 如果節點 $v$ 已經被選擇了那麼 $v$ 相鄰的節點都不能再被選擇