男女求婚配對活現演算法

【本報訊】蓋爾─沙普利演算法可以令資源最終得到有效的配對,其中一個例子以男女配對作解釋。假設男士和女士各十位,男士們在第一輪向自己最喜歡的女士求婚,被求婚的女士可從求婚者中,選出最喜歡的那位男士,與他訂婚,但是往後亦可以背約。

而沒有人求婚的女士,只可以等。在第一輪求婚失敗的男士,可在第二輪向次選求婚。已訂婚的女士如遇到更心儀的對象,可以貪新忘舊。此步驟一直重複,就會形成十對伴侶。而在這制度下,每個人都得到了符合自己要求的選擇。這個例子可以轉為由女士向男士求婚,得出的結果也一樣。

另一例子為學生申請入學,每個學生申請第一志願,校方依照他們的偏好排序,依序排學位予學生,學位滿額後則拒絕其他學生。沒有學位的學生則繼續向下一個志願提出申請,如此類推,結果學生仍然可以得到選擇範圍內的學位。