Smp

稳定婚姻问题 Stable Marriage Problem定义 两个集合men、women数量相等，每个人持有对异性的好感度顺序表。现在假定要对这n对进行匹配，如果某种匹配存在同时满足以下三个条件的m-w对(blocking-pair)，则认为此匹配是不稳定的：1)m和w目前没有订婚（意味着它们的订婚对象是别人） 2) 在m的优先级列表中，w的级别比当前订婚对象高 3) 在w的优先级列表中，m的优先级比当前订婚对象优先级高。 反之则称这个匹配是稳定的。在这样一个场景中求解稳定订婚关系的问题，称之为稳定婚姻问题 常见变种 SMI:(SM with Incomplete lists) SMT:(SM with Ties) 按照稳定条件依次减弱 super-stability strong stability weak stability: 总是存在解，并能在多项式时间内解决 SMTI(SM with Ties and Incomplete lists) 三种稳定关系定义，同上 super/strong关系，存在算法可以确定一个问题是否有解，以及求出一个解，super stability时间复杂度O(a), strong stabilityO(na)， a表示所有优先级列表的整体长度（2n^2如果所有优先级列表都是完整的），且所有的解都具有相同的大小 weak stablity，任何情况下都存在一个稳定匹配，并且可以在O(a)时间内找到，但是解的大小可以有多个，求解其中最大的那个是NP-Hard的 经典解法 Gale-Shapley Algorithm algorithm stable_matching is Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to do w := first woman on m's list to whom m has not yet proposed if w is free then (m, w) become engaged else some pair (m', w) already exists if w prefers m to m' then m' becomes free (m, w) become engaged else (m', w) remain engaged end if end if repeat 按轮次进行 ...