演算法助集體相親配對

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

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

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