안정적인 일치의 카운터 예

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)
단계 1 : W1과 m2 일치하고 (W1, m2) (w2, m1) (w3, m3)
스텝 2 : w1과 m3이 일치하면, (w1, m3) (w2, m1) (w3, m2) (w1, m1) (w3, m2) 단계 3 : w2와 m3이 일치하면, (w1, m1) (w3, m2)
단계 4 :)

4 단계가 완료되면 일치가 초기 상태로 바뀌며 무한 루프가 발생합니다.

Answer 2

당신이 말하는 알고리즘은 선호도를 전혀 고려하지 않고 무작위 매칭입니다. 이 알고리즘에서 한 파트너는 더 높은 우선 순위를 가질 수 있기 때문에 안정적인 모든 일치가 안정됩니다.

안정적인 일치는 솔루션이 모든 사람에게 공평한 정의입니다.

또한이 알고리즘은 무한 루프를 가능하게하는 이전 일치를 피하는 것에 대해서는 언급하지 않습니다.