问稳定匹配的最坏情况

EN

Gale-Shapley算法是一种用于解决稳定匹配问题的方法，它既保证了完全匹配，又保证了不稳定。这个算法由重复的提议和结束组成，当每个人都配对时。在这种稳定婚姻问题的情况下，男人会按她们的喜好顺序向女人求婚。如果这个女人不是一对，她必须接受这个求婚。如果女人是一对的，如果男人在她的求婚偏好列表中比她现在配对的男人更高，她就可以接受另一个求婚。一旦每个女性都被提名(因此每个人都被配对了)，算法就结束了。

您提到的首选项列表是稳定匹配问题的最坏情况的一个示例。要了解它是如何工作的，可以将其绘制出来并逐个步骤运行。首先，m1将向w1求婚，w1必须接受，因为她目前不是一对。m2将向w2提出建议，m3将向w3提出建议，m4将向w4提出建议。正如你所看到的，目前每个男人都有他们的第一偏好女人，每个女人都有他们的第五偏好男人(除了m5和w5)。该算法之所以继续，是因为w5没有配对。

接下来，m5将向w1求婚。w1之所以能够接受，是因为她对m5的排名比m1高。现在，m1是无与伦比的，所以他向w2求婚。w2接受了，因为在她的偏好列表中，m1的排名比m2高。这样继续下去，你会注意到每个男人都与他们的第二个首选女人配对，每个女人都接受他们的第四个首选男人的提议(除了w5)。该算法继续进行，因为w5仍未配对。

一旦您完成了整个算法，您将注意到最终的配对是m1-w5、m2-w1、m3-w2、m4-w3和m5-w4。每个男人都有他们的第四个偏好的女人(除了m1，他有他的第五个偏好)，每个女人都有他们的第一偏好的男人。

请注意，每个人都将w5作为他们的第五个偏好。正因为如此，每个人在向w5提出报价之前，都会仔细看一遍他们的整个名单。w5的首选项列表可以是任何顺序，但这仍然是最坏的情况。您提到的首选项列表只是最坏情况的一个示例，但还有其他变体遵循与此相同的逻辑。

这里有一个更正式的方法来证明最坏的情况。任何女性都不能收到超过n个提案，但一旦每个女性收到一个提案，算法就会停止。因此，在最坏的情况下，除了一个(n -1个女人)之外，每个女人都会收到来自每个男人(n)的求婚。最后一位女士将收到1份提案，最终将结束算法。将这些组合在一起，当n(n-1) +1个提议被扩展时，最坏的情况就会发生。在你的例子中，4个男人结束了他们的第四个偏好(每个4个提议)，1个男人结束了他的第五个偏好(5个提议)。4*4 +5= 21，等于将n=5插入n(n- 1 ) +1。

我希望这能帮到你。