The Dinitz Problem (편집) (6)

(편집 필터 규칙)

=== Stable Matching ===
'''Definition''' 이분그래프 [math(G=(U \cup V, E))]에서 '''matching''' [math(M \subset E)]은 임의의 두 원소도 공통된 끝점을 가지지 않는 변의 집합을 말한다. [math(U)]의 각 원소 [math(u)]에 대하여 [math(u)]와 이웃한 꼭짓점들의 순위 [math(N(u,v_i))]와 [math(V)]의 각 원소 [math(v)]에 대하여 [math(v)]와 이웃한 꼭짓점들의 순위 [math(N(v,u_i))]가 정의되어있다고 하자. 예를 들어, [math(u)]와 연결된 두 꼭짓점 [math(v_1, v_2)]에 대하여 [math(N(u,v_1)>N(u,v_2))]임은 [math(u)]가 [math(v_1)]보다 [math(v_2)]를 더 선호함을 뜻한다. 이 때, 임의의 [math((u-v) \in E \setminus M)]에 대하여 [math((u-v’) \in M,\ N(u,v)<N(u,v’))]인 [math(v’)] 또는 [math((u’-v) \in M,\ N(v,u)<N(v,u’))]인 [math(u’)]이 존재하는, 즉 ‘[math(u-v)]라는 짝이 새로 생성되어 손잡고 달아나지 않을’ [math(M \subset E)]를 [math(G)]의 '''stable matching'''이라고 한다.

Stable matching을 찾는 방법에는 Gale-Shapley Algorithm이 있다. 이는 다음과 같이 구성된다.[* 이해를 돕기 위해 실제로 짝을 짓는 상황을 가정하겠다.]

1. [math(R \subset U)]를 연결된 변이 존재하는 [math(U)]의 원소의 집합으로 정의한다.

2. [math(R)]의 짝이 없는 원소들이 연결되어있는 [math(V)]의 고백해보지 않은 원소들 중 우선순위가 가장 높은 원소에게 다같이 고백한다. 고백받은 [math(V)]의 원소들은 (있다면) 현재 자신의 짝과 자신에게 고백한 [math(U)]의 원소들 중 우선순위가 가장 높은 원소를 선택하여 자신의 짝으로 하고 나머지를 찬다.

3. 현재 짝이 없는 [math(R)]의 원소들 중 자신의 마지막 우선순위에 있는 원소에게 아직 고백을 해보지 않은 원소들로 [math(R)]을 다시 구성한다.

4. [math(|R|=0)]이라면 알고리즘을 종료하고, 공집합이 아니라면 2로 돌아가 반복한다.

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)

Stable matching을 찾는 방법에는 Gale-Shapley Algorithm이 있다. 이는 다음과 같이 구성된다.[* 이해를 돕기 위해 실제로 짝을 짓는 상황을 가정하겠다.]

1. [math(R \subset U)]를 연결된 변이 존재하는 [math(U)]의 원소의 집합으로 정의한다.

3. 현재 짝이 없는 [math(R)]의 원소들 중 자신의 마지막 우선순위에 있는 원소에게 아직 고백을 해보지 않은 원소들로 [math(R)]을 다시 구성한다.

4. [math(|R|=0)]이라면 알고리즘을 종료하고, 공집합이 아니라면 2로 돌아가 반복한다.

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.