# 演算法_王紹睿
## Stable Matching
### Introduction
男女各有 $n$ 個人，並且每一個人會有一個異性喜好程度的表

而我們要找到一種 stable 的配對方式（男對女）
stable: 不會出現男女互相喜歡對方更勝於配對結果

以下就**不是一個 stable** 的配對
綠色代表配對的結果，黃色的格子代表還有更好的配對方式
（因為男生有更喜歡的女生，且那個女生也更喜歡新的男生）

### Solution

# 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
這個演算法會中止

w = highest ranked woman in m's list to whom m has not yet proposed

從這一行來看，可以得知每一次求婚都會產生一組配對
- 如果女生是 free 的
則無條件接受男生的求婚，增加一組配對
- 如果女生是 engaged 的
不論是拒絕還是接受（悔婚），總配對數都不變

所以一定可以在 $n^2$ 之後停止迭代

#### Perfection
每一個人都會被配對
這邊用的是反證法，假設有一個男生是 free 的
再來看看迭代的中止條件

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$ 相鄰的節點都不能再被選擇