稳定匹配算法详解与复杂度分析

"《算法设计与分析》课程笔记1，讲解了稳定匹配算法及其相关概念，包括inversion、最近点对问题，并提供了算法的伪码及复杂度分析。" 在算法设计与分析中，稳定匹配是一种重要的理论，特别是在分配问题和匹配问题中。这里讨论的是稳定婚姻问题（Stable Marriage Problem），其中稳定匹配算法是一个核心概念。稳定匹配旨在寻找一种配对方式，使得没有任何一对男女愿意互相替换当前的伴侣，即不存在不稳定的匹配。 稳定匹配算法的思想基于以下原则：当一个人没有匹配时，他会按照自己的偏好列表去寻找当前未匹配或比现有伴侣更喜欢的人。算法的伪码通常包含一系列的循环，直到所有人均找到匹配。 算法复杂度分析指出，最多经过N^2次的while循环，稳定匹配算法就能结束。这是因为每个男性最多会向N个不同的女性求婚，而有N个男性，所以总求婚次数不会超过N^2。算法的正确性和稳定性可以通过归纳法和反证法来证明。 正确性证明的关键在于，由于男女人数相等，如果存在未匹配的男性M，他可以向未匹配的女性W求婚，W会接受，因为他们都没有其他匹配。进一步，假设存在不稳定的匹配，如W-M和X-Y，但实际上W和Y更喜欢对方，通过逻辑推理可以发现这种假设会导致矛盾，从而证明了匹配的稳定性。 在实际实现稳定匹配算法时，通常会用到队列来存储单身男性，以便于每次循环选择一个男性进行求婚。此外，还需要两个二维数组分别记录男女的偏好列表，以及一个大小为N的数组记录男性求婚的次数，以加速查找过程。 稳定匹配的一个特性是，对于每一个男性来说，他在稳定匹配中得到的伴侣是所有稳定匹配中他能获得的最好的。这可以通过引入valid-partner的概念来证明，即在稳定匹配中的伴侣。如果某个男性在最优匹配S*中不是最优选择，那么可以找到一个更好的稳定匹配S，但这会导致S的不稳定，因为在这种情况下，至少有一对男女更喜欢彼此，违反了稳定性的定义。 最后，文中提到了Woman-passive策略，即在某些情况下，如果匹配不是man-optimal（对男性最优），可能存在矛盾，但这进一步证实了稳定匹配的逻辑严密性和正确性。 这篇课程笔记深入探讨了稳定匹配算法的原理、证明、实现细节和特性，为理解算法设计与分析中的这一重要概念提供了详尽的阐述。