algorithm - 稳定匹配的反例

Question

我目前正在阅读一本算法书并遇到了稳定匹配问题。我想到了一个我很好奇的问题，但是这本书没有回答。问题是:
对于任何匹配，如果它不稳定，选择任何阻塞对(w，m)，并匹配它们。并且还匹配他们以前的合作伙伴。并重复。这是达到稳定匹配的正确算法吗？
看来答案是否定的。但是我想不出反例。有没有人可以帮忙？

Answer 1

我想我找到了答案。假设我们有 3 名女性和 3 名男性。他们的偏好列表是:
w1: m3 > m2 > m1
w2: m2 > m3 > m1
w3:不关心

m1:不关心
m2: w1 > w2 > w3
m3: w2 > w1 > w3

初始匹配:(w1,m1) (w2,m2) (w3,m3)
第一步:w1和m2匹配，然后(w1,m2) (w2,m1) (w3,m3)
第二步:w1和m3匹配，然后(w1,m3) (w2,m1) (w3,m2)
第三步:w2和m3匹配，然后(w2,m3) (w1,m1) (w3,m2)
第四步:w2和m2匹配，则(w1,m1) (w2,m2) (w3,m3)

4步后，匹配进入初始状态，进入死循环。