稳定婚姻问题

可以通俗的理解为有n个男生，n个女生，每个人都每个异性都有 一个好感度，要求两两配对结为夫妻，使不存在夫妻uv和ab，满足u对b的好感度大于u对v的好感度，b对u的好感度大于b对a的 好感度。求这种稳定婚姻的方案。

Gale-Shapley算法

• 首先，男生需要按照希望与之交往的顺序给所有女生排序，即最理想 的女友排在最前、最不理想的放在最后。同样，每个女生也需要给男 生排序。接着，男生将按照自己的名单一轮一轮地去追求喜欢的女生， 女生也将按照自己的名单接受或拒绝对方的追求。

• 第一轮，每个男生都向自己名单上排在首位的女生表白。此时，一个 女生可能面对的情况有三种：没有人跟她表白、只有一人跟她表白、 有不止一人跟她表白。在第一种情况下，这个女生什么都不做，继续 等待即可；在第二种情况下，女生接受那个人的表白，答应暂时和他 做男女朋友；在第三种情况下，女生从所有追求者中选择自己最喜欢 的那一位，答应和他暂时做男女朋友，并拒绝其他所有的追求者。

• 第一轮结束后，有些男生已经有女朋友了而有些男生仍然是单身狗。在第二轮表白 行动中，每个单身男都会从所有还没拒绝过自己的女生中选出自己最喜欢的那一个， 并向她表白，不管她现在是否是单身。和第一轮一样，每个被表白的女生需要从表 白者中选择最喜欢的男生，并拒绝其他追求者。注意，如果这个女生当前已经有男 朋友了，当她遇到了更好的追求者时，她将毫不犹豫地和现男友分手，投向新追求 者的怀抱。这样以来，一些单身狗将脱单，而一些倒霉的恩爱狗（男）也会被分手， 重新进入单身狗的行列。

• 在以后的每一轮中，单身狗们将发扬愈挫愈勇的顽强精神，继续追求列表中的下 一个女生；女生则从包括现男友在内的所有追求者中选择最好的一个，并给其他所 有追求者发好人卡。这样一轮一轮地进行下去，直到某个时刻所有人都不再单身， 那么下一轮将不会有任何新的表白，每个人的对象也都将固定下来，整个过程自动 结束——此时的搭配就一定是稳定的了。