관리자      

         

   프로포즈 알고리즘      
신문에서 펀 글인데, 프로포즈 알고리즘... 재밌네요..

‘연애결혼의 아버지는 실수, 어머니는 불가피성이다.’
독일 철학자이자 시인인 프레드리히 니체의 이 격언에 혹시 고개를 끄덕이지는 않는가. 결혼이라는 인생 중대사에 특별한 관심을 보여온 동서고금 각계의 학자들에서 수학자 역시 빠질 수 없다. 결혼식이 많은 계절, ‘프로포즈 알고리즘’, 혹은 ‘전통결혼 알고리즘’이라 불리는 수학적 전산 과정을 통해 결혼과 선택의 상관관계를 알아보자.

프로포즈 알고리즘’은 무엇인가?

제 짝을 찾아 결혼에 이르는 과정을 수학적 알고리즘으로 설명한 ‘프로포즈 알고리즘’은 사랑하는 사람을 적극적으로 찾아가는 것과 자신에게 찾아오는 사람 중 최선의 배우자를 선택하는 것 가운데 어느 쪽이 더 유리한지에 초점을 맞춘다. 미국의 수학자 게일과 셰이플리가 정리한 이 공식이 ‘전통결혼 알고리즘(TMAㆍtraditional marriage algorithm)’라고도 불리는 이유는 남성이 맘에 드는 여성을 찾아간다는 가정으로부터 시작하기 때문이다.

TMA의 진행방식은 다음과 같다.

1. 남성이 결혼할 수 있는 여성 후보 중 가장 마음에 드는 사람에게 찾아가 프로포즈를 한다.

2. 여성은 자신에게 찾아온 남성들 중 더 나은 사람에게 ‘일단 대기’하라고 하고 나머지에게는 ‘나와 절대 결혼할 수 없으니 돌아가라’고 한다.

3. 탈락한 남성은 처음 선택한 여성 다음으로 마음에 드는 여성에게 다시 프로포즈를 한다. 이때 여성이 전에 택한 이보다 다시 도전한 사람이 좋으면 전에 택한 이에게 ‘돌아가라’고 한다.

4. 위의 방법을 ‘짝이 없는 남성’이 더 이상 없을 때까지 반복한다.

이 식은 남성과 여성의 수가 한정돼 있고 동성애, 혹은 양성애 커플이 없을 경우에 한해 어느 선에 이르면 반드시 끝나게 돼 있다. 한 사람이 거부를 당한다는 것은 결국 한 쌍이 맺어져 전체 집합에서 사라지는 것을 뜻하므로 수학적 식으로는 n명의 남성과 여성이 각각 있을 때 n2_n+1번 이내에 알고리즘은 끝난다. 또한 양측의 숫자가 각각 n일 때 이들이 자신의 짝을 만날 수 있는 평균 도전 횟수는 n logn 이다.

이상형을 만날 확률, 누가 더 높을까

간단하게 보이는 이 알고리즘은 실제로 세계 유명 결혼회사나 직업소개소 등에서 사용되는 컴퓨터 프로그램에서 사용하는 것이다. 사회에서 이 프로그램이 효과적으로 운영될 수 있으려면 제안을 받아들이거나 거부할 수 있는 기한을 짧게 잡아야 하는 것이 관건. 실제로 1940년 초 미국의 병원들은 이 같은 시스템으로 레지던트를 뽑았는데 선택 시간이 제한되지 않자 심하게는 졸업하기도 전인 2년 전부터 선발절차를 시작해야 했다. 선발 절차가 이토록 오래 걸리자 실제로 병원 측은 후보 레지던트에게 약 12시간 정도의 시간을 주고 결정을 강요하기도 해 문제가 됐다.

이 알고리즘은 언뜻 살펴보면 찾아오는 이를 거절하거나 받아들일 수 있는 선택권을 지닌 여성, 혹은 고용자 측이 훨씬 유리해 보인다. 그러나 수학자들이 복잡한 증명 과정을 거쳐 내린 결론은 이 경우 ‘자신의 이상형과 결혼하는 횟수는 남성이 훨씬 높다’는 것. 이들은 정해진 숫자의 후보 안에서 거절당한다는 위험부담이 있더라도 선호하는 짝을 자신이 찾아 나설 때 원하는 짝을 만날 확률이 커진다고 말한다. 이 증명의 골자는 ‘원하는 짝을 찾아가 거절 당하는 위험 부담이 원하는 짝이 자신을 찾아오지 않을 부담보다 훨씬 크다’는 것. 이들의 증명대로 자신의 짝에게 용기 있게 도전해 얻는 배우자에 대한 만족도가 훨씬 높다면 요즘 젊은 여성들의 적극적인 자세는 남성보다 여성의 행복 지수를 높여주는 셈이다.



90
  통영에서.. [648]

관리자 
2006/04/21 714
89
  봄날 벛꽃....

관리자 
2006/04/18 749
88
  전주에서... [792]

관리자 
2006/03/26 799
87
  무주 스키장에서..

관리자 
2006/03/15 802
86
  횡성 키장에서..

관리자 
2005/12/21 753
85
  계룡산에서..

관리자 
2005/10/29 741
84
  서울 남산, 청계천에서.. [2]

관리자 
2005/10/15 407
83
  대천해수욕장에서..

관리자 
2005/10/04 354
82
  대전 엑스포 다리

관리자 
2005/09/03 357
81
  작년 안동, 부석사에서.. [1514]

관리자 
2005/06/08 433
80
  간절곳에서.. [18]

관리자 
2005/05/29 368
79
  운죽정의 야경 [18]

관리자 
2005/05/19 442
78
  눈오던 날의 풍경 [19]

관리자 
2005/03/12 397
77
  작년 10월에 있었던 진주 유등 축제 [19]

관리자 
2005/01/24 399
76
  눈 오던 날 [18]

관리자 
2005/01/23 367
75
  일본 도쿄 여행기 - 2 [19]

관리자 
2005/01/02 451
74
  일본 도쿄 여행기 - 1 [18]

관리자 
2005/01/02 414

  프로포즈 알고리즘 [22]

관리자 
2004/09/30 621
72
  카메라 조리개를 조여서 불빛을 별모양처럼.. [18]

관리자 
2004/09/24 422
71
  가을하늘 [17]

관리자 
2004/09/14 359
1 [2][3][4][5]    

Copyright 1999-2018 Zeroboard / skin by ZINA / M