Gale—Shapley匹配的推广 |
| |
作者姓名: | 连广昌 朱顺荣 |
| |
作者单位: | 金陵职业大学(连广昌),南京理工大学理学院(朱顺荣) |
| |
摘 要: | 该文推广了Gale-Shapley匹配的男孩-最优算法。证明了当男孩挑选时,允许某些男孩可以不挑选,则G-S匹配的最大步数为n^2-n+1。给出了一般情形下的Gale-Shapley匹配,即有m个男孩,n个女孩时,男孩-最优算法的最大步数是m(m-1)+1,或n(m-1)+1;女孩-最估算法的最大步数是n(n-1)+1,或m(n-1)+1。
|
关 键 词: | 男孩-最优匹配 G-S匹配 完全两部图 |
本文献已被 CNKI 维普 等数据库收录! |
|