深圳网站设计制作元免费发链接的网站

稳定匹配

根据医院和医学院学生的一系列偏好，设计一套自我执行的入学程序。
非稳定配对： 若x更喜欢 y 而不是指定的医院。或者y更喜欢 x 而不是其入院的学生，则x和 医院 y 是不稳定的:
稳定分配。没有非稳定配对的分配。

稳定匹配问题

参与者对异性成员的评价
每个男人按照优先顺序从最好到最坏的顺序列出女人。
每个女人按照优先顺序从最好到最坏的顺序列出男人

完美匹配与稳定配对

完美匹配 perfect matching

• 指一个表中的每个条目都恰好匹配另一个表中的一个条目，反之亦然。在课堂上的例子中，这意味着每个男人和一个女人匹配，每个女人和一个男人匹配。

稳定匹配 stable matching

• 是没有不稳定对的完美匹配。换句话说，这既要求与某项匹配的条目数量(仅为1比1)，也要求不能有一对(X,Y)使得X在当前匹配中更喜欢Y，而Y在当前匹配中更喜欢X。

所以完美匹配只是说可以匹配的元素的数量，但它没有说匹配需要是稳定的。

不稳定配对

同桌问题

在同桌问题中，稳定匹配不总是