RSS 리더를 읽다가 10여년 전 배웠던 알고리즘을 소개하는 글을 봤습니다. 당시 이 알고리즘을 배우고 나서, 혼자 마음 속으로 명명하기로 Happy Marriage Algorithm 이라 했었는데, 실제로 이 문제의 이름은 Stable Marriage Problem (SMP) 이더군요.

http://en.wikipedia.org/wiki/Stable_marriage_problem

문제는 간단합니다.

남자와 여자가 같은 수가 있으며, 모든 남성과 여성은 모두 이성에 대한 선호도를 Linear Order 로 가지고 있다고 가정합니다. 이 때 남자와 여자간에 일대일 대응을 주었습니다. 만약 서로 대응되지 않은 어떤 남성과 어떤 여성이 서로에 대한 선호도가 각자의 대응된 이성보다 높게 되면, 이 상태를 불안정하다고 합시다.

주어진 선호도에 따라서 모두가 안정되게 대응시킬 수 있을까요?

해결 방법은 다음의 링크를 눌러서 글을 읽어 보시길 바랍니다.

http://intothereign.tistory.com/194

이 알고리즘의 단점은 알고리즘 종료 시점을 미리 알 수 없어서 Time complexty 를 계산할 수 없다는 점입니다. 하지만 여러가지 형태의 다대다 대응 모델로 쉽게 확장 할 수 있는 장점이 있습니다.

그나저나 이런 알고리즘으로 모두가 행복해 질 수 있을까요?

'Thoughts > Math' 카테고리의 다른 글

재밌는 시외버스 가격  (3) 2009.08.26
적분 문제  (4) 2009.06.25
2014년 국제 수학자 대회 (ICM) 서울 유치  (0) 2009.04.23
정수일까? 아닐까?  (0) 2009.02.12
Ramanujan's infinitely nested radicals problem  (2) 2009.01.17

+ Recent posts