最近我對於 Graph 的節點匹配特別感興趣，因此複習 Gale-Shapley 經典演算法，記錄一點心得。
D. Gale 和 L. S. Shapley 於 1962 年發表的論文 "College Admissions and the Stability of Marriage" 內，討論穩定匹配的問題，而發展出 Gale-Shapley 演算法。此演算法討論的問題可簡化如下。
假設有兩個 Group，分別為 Group 1 跟 Group 2。已知：
Gale-Shapley 的目標是在此情況下，利用 Rank 評比求穩定匹配。
所謂穩定匹配（Stable Match），表示 Group 1 內的每個 Vertex 只能搭配唯一一個 Group 2 內的 Vertex。同時，假設在穩定匹配下 A 與 E 搭配成一對，則在 Group 2 內找不到其他 Vertex V 滿足：
A 對 V 的評比高於 A 對 E 的評比且 V 對 A 的評比又高於 V 當前的搭配對象。
如果對每一組搭配皆符合上述這種條件，稱為穩定匹配。
將 Fig 1. 的兩個矩陣合併可以產生一個新矩陣：
Fig 2. 中把兩個 Rank 組成一個 Pair。Pair 中第一個數字代表 Group 1 中的 Vertex 對 Group 2 成員的評比，第二個數字代表 Group 2 對 Group 1 的評比。因此整個系統可用二分圖表示，用兩個 Rank 組成的 Pair，當作此二分圖 Edge ，並建立 Graph 資料結構。
Gale-Shapley 演算法可在此二分圖上尋找穩定匹配，Pseudo Code 如下：
Gale-Shapley (Group_1, Group_2)
1 clean all match status.
2 for each vertex v in Group_1 do
3 while (v has not been matched)
4 pop vertex v_decide with max rank in the rank list of v
5 if v_decide has not been matched
6 match(v, v_decide)
7 else
8 if rank(v) of v_decide > rank(v_decide.partner) of v_decide
9 match(v, v_decide)
10 unmatch(v_decide.partner)
11 else continue
12 return match status
由於此演算法對於 Group 1 內每個成員，迴圈最多需 n 次走訪，因此複雜度為 O(n*n) 。值得注意的是這個演算法有兩種解，上面展示的 Pseudo Code 是以 Group 1 的角度優先選擇 match 對象，如果換為 Group 2 先選，會有另一組解，但有時兩組解會相同。
[Reference]
Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15.
D. Gale 和 L. S. Shapley 於 1962 年發表的論文 "College Admissions and the Stability of Marriage" 內，討論穩定匹配的問題，而發展出 Gale-Shapley 演算法。此演算法討論的問題可簡化如下。
假設有兩個 Group，分別為 Group 1 跟 Group 2。已知：
- Group 1 跟 Group 2 內的 Vertex 數目皆為 n 。在此假設 n = 3 ，且 Group 內的 Vertex 為 A、B 及 C。Group 2 內有 D、E 和 F 三個 Vertex 成員。
- 可定義 Rank 排名，來描述 Group 1 內的 Vertex 對 Group 2 內 Vertex 的關注程度。舉例來說，若 A 對於 F 關注程度最高，其次是 D 最後是 E，則對 A 而言 F 的 Rank 為 1，而 D 的 Rank 是 2，最後 E 的 Rank 是 3 。同樣的，Group 2 內的 Vertex 也對 Group 1 做 Rank 評比而得到如下的矩陣：
 |
Figure 1. 利用 Rank 表達 Group 之間的 關注程度。
左邊為 Group 1 對 Group 2 的 Rank 評比，右邊為 Group 2 對 Group 1 評比
|
所謂穩定匹配（Stable Match），表示 Group 1 內的每個 Vertex 只能搭配唯一一個 Group 2 內的 Vertex。同時，假設在穩定匹配下 A 與 E 搭配成一對，則在 Group 2 內找不到其他 Vertex V 滿足：
A 對 V 的評比高於 A 對 E 的評比且 V 對 A 的評比又高於 V 當前的搭配對象。
如果對每一組搭配皆符合上述這種條件，稱為穩定匹配。
將 Fig 1. 的兩個矩陣合併可以產生一個新矩陣：
 |
| Figure 2. 將 Gruop 1 跟 Group 2 各自的 Rank 合併成一對（Pair），形成一個矩陣 |
Gale-Shapley 演算法可在此二分圖上尋找穩定匹配，Pseudo Code 如下：
Gale-Shapley (Group_1, Group_2)
1 clean all match status.
2 for each vertex v in Group_1 do
3 while (v has not been matched)
4 pop vertex v_decide with max rank in the rank list of v
5 if v_decide has not been matched
6 match(v, v_decide)
7 else
8 if rank(v) of v_decide > rank(v_decide.partner) of v_decide
9 match(v, v_decide)
10 unmatch(v_decide.partner)
11 else continue
12 return match status
由於此演算法對於 Group 1 內每個成員，迴圈最多需 n 次走訪，因此複雜度為 O(n*n) 。值得注意的是這個演算法有兩種解，上面展示的 Pseudo Code 是以 Group 1 的角度優先選擇 match 對象，如果換為 Group 2 先選，會有另一組解，但有時兩組解會相同。
[Reference]
Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15.
留言
張貼留言