최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기The journal of the institute of internet, broadcasting and communication : JIIBC, v.18 no.4, 2018년, pp.149 - 154
There is well known algorithm is a Gale-Shapley algorithm(GSA) for stable marriage problem. The GSA is performed as each man propose to his most favorite woman(MP), then the woman accepts more than one proposal rejects all but her favorite from among those who have proposed to her. This algorithm al...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
man proposed 매칭 알고리즘은 항상 어떤 결과를 얻는가? | 이를 MP(man proposed)라 하자. MP는 항상 안정된 매칭 결과를 얻는다. 왜냐하면, 남성이 가장 선호하는 여성을 선택하고, 여성에게 거절당한 남성이 차선책으로 선택하여 불안정한 경우가 발생하면 여성 쪽에서 보다 선호하는 남성을 선택함으로써 불안정한 경우를 차단하는 결과를 얻기 때문이다. | |
안정된 결혼문제에 대하여 유일하게 알려진 알고리즘은 무엇인가? | 안정된 결혼문제에 대해서는 Gale과 Shapley 알고리즘(GSA)이 유일하게 알려져 왔다. 이 알고리즘은 남성이 자신이 가장 선호하는 여성에게 청혼하면 여성이 수락/거절하는 방식(MP)으로 남성 최적-여성 최악의 결과이지만 항상 안정된 매칭 결과를 얻는다. | |
STA 에 대하여 Gale과 Shapley이 제안한 알고리즘은 어떤 방식으로 설계되어 있는가? | STA에 대해서는 Gale과 Shapley[1]가 1962년에 알고리즘을 제안하였다. 이 알고리즘은 남성(지원자)이 가장 선호하는 여성에게 청혼(propose)하면 여성은 자신에게 청혼한 남성이 1명이면 무조건 청혼을 받아들이고(accept), 2명이면 보다 싫어하는 사람의 청혼을 거절(reject)한다. 청혼을 거절 당한 남성은 다음으로 선호하는 여성에게 다시 청혼을 한다. 이와 같은 방법으로 모든 남성들에 알고리즘을 수행하여 1:1의 n쌍 매칭이 결정되면 알고리즘이 종료된다. 이를 MP(man proposed)라 하자. |
D. Gale and L. S. Shapley, L. S. "College Admissions and the Stability of Marriage," American Mathematical Monthly, Vol. 69, No. 1, pp. 9-14, Jan. 1962, doi:10.1080/ 00029890.1962.11989827
R. W. Irving, P. Leather and D. Gusfield, "An Efficient Algorithm for the Optimal Stable Marriage," Journal of the ACM, Vol. 34, No. 3, pp. 532-543, Jul. 1987, 10.1145/28869.28871
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.