짝짓기 알고리즘(TMA, 섀플리 게일 알고리즘) 자바스크립트

얼마전에 네이버 캐스트에서 섀플리-게일 알고리즘에 대한 글을 읽게 되었다. 짝을 지어주는 알고리즘이라고 하니 꽤 흥미가 갔다. 찾아보니 섀플리-게일 알고리즘은 TMA라는 이름을 가지고 있었다. TMA(전통적인 결혼 알고리즘)은 안정적인 결혼이 이루어지도록 짝을 지어주는 알고리즘이다. 나는 아래 링크 글을 바탕으로 구현했다. TMA 알고리즘이 어떻게 동작하는지 상세하게 설명하고, 왜 TMA알고리즘이 항상 안정적인 커플을 생성할수 있는지, 왜 TMA 알고리즘이 남성(구혼자)에게 더 유리한지에 대한 수학적 원리도 실려있다.

참고글 링크 : http://blog.koreadaily.com/view/myhome.html?fod_style=B&med_usrid=jaeok9876&cid=620916&fod_no=3

규칙은 매우 간단하다. 

시작하기 전에 N명의 남성과 N명의 여성은 각자 가장 마음에 드는 상대방부터 차례로 적은 리스트를 만든다. 그리고 아래 과정을 반복한다.

1. 매일 아침 남성들은 자신들의 목록에서 제일 위에 있는 여성의 집에 찾아가서 프러포즈한다.

2. 여성은 자기에게 프러포즈한 남성 중 리스트에서 가장 위에 있는 남성에게는 "내일도 찾아오세요", 그 외의 남성에게는 "다른 여성을 찾아보세요"라고 거절한다.

3. 거절당한 남성은 거절당한 여성을 리스트에서 지운다. 

4. 거절당한 남성이 한명도 없다면 종료한다.

모든 과정은 최대 N^2일 안에 끝나며, 과정이 끝날 때는 모든 남성과 모든 여성이 안정적으로 짝이 지어진다. 이 알고리즘을 살펴보면 언듯 보기에는 찾아온 남성을 마음대로 고를 수 있는 여성이 더 유리해 보이지만, 사실 남성이 더 유리하다. 자세한 것은 위 글 참고.

전체 소스코드(자바스크립트) : TMA.html

결과를 보면 역시 거의 비슷한 가치의 남성과 여성이 짝지어지는 것을 볼 수 있다. TMA 알고리즘은 현재 병원과 레지던트의 연결, 기숙사 방배정 등에 사용된다고 한다.

소스코드 설명:

먼저 남성과 여성을 만들어보자.

for(var i=0;i<population;i++){

    boys[i] = {};

    boys[i].value = Math.floor(Math.random() * population); //가치

    boys[i].list = [];  //프러포즈 리스트

    girls[i] = {};

    girls[i].value = Math.floor(Math.random() * population); //가치

    girls[i].list = []; //프러포즈 리스트

    girls[i].engaged = false; //약혼 했는지

    girls[i].engagedboy = null; // 약혼 상대 번호

}

남성은 간단하게 프러포즈 리스트, 값 두가지의 정보만 가지고 있다.

여성은 리스트, 약혼 여부, 약혼 상대의 번호(이름) 세가지의 정보를 가지고 있다. 가치는 0에서 인구수 값 사이에서 랜덤으로 정해진다.

이제 각각의 남성과 여성은 각자 리스트를 만들어야 한다. 

(NAME은 상수 0, VALUE는 상수 1이다.)

//목록 작성

for(var i=0;i<population;i++){

  for(var j=0;j<population;j++){

    boys[i].list[j] = [];

    girls[i].list[j] = [];

    boys[i].list[j][NAME] = j;

    boys[i].list[j][VALUE] = girls[j].value;

    girls[i].list[j][NAME] = j;

    girls[i].list[j][VALUE] = boys[j].value;

  }

  boys[i].list.sort(function(a,b){return a[VALUE]-b[VALUE];});

  girls[i].list.sort(function(a,b){return a[VALUE]-b[VALUE];});

}

우선 리스트에 상대방의 값과 번호를 모두 적고, 그 다음 sort 함수를 이용해서 리스트를 작은것부터 큰 순서 대로 정렬해준다. 그러므로 리스트 맨 끝에 있는 사람이 가장 선호하는 상대방이 된다. 이렇게 한 이유는, 앞에서 부터 지우는것 보다는 뒤에서 부터 짜르는게 더 쉬울 것 같아서 그렇게 했다.

// 시작

for(var i=0;i<population**2;i++){

  for(var j=0;j<population;j++){

    var proposegirl = girls[boys[j].list[parseInt(boys[j].list.length)-1][NAME]];

    if(!proposegirl.engaged || boys[proposegirl.engagedboy].value < boys[j].value){

      proposegirl.engaged = true;

      proposegirl.engagedboy = j;

    }

  }

  //거절되었거나 파혼당했다면 목록에서 제외

  for(var j=0;j<population;j++){

    var proposegirl = girls[boys[j].list[parseInt(boys[j].list.length)-1][NAME]];

    if(proposegirl.engagedboy != j){

      boys[j].list.pop();

    }

  }

}

간단하게 프로포즈할 여성(리스트 맨 끝에 있는 여성)의 약혼 상대 남성의 가치보다 구혼한 남성의 가치가 더 높다면 구혼한 남성으로 교체한다. 만약 남성이 거절되었거나 파혼당했다면 pop()함수를 이용해 리스트의 마지막을 잘라버려서 목록에서 제외한다. 이런 식으로 계속 진행한다면 끝난다.