earticle

영어

In this paper I propose a simple optimal solution seeking algorithm to a stable marriage problem. The proposed algorithm firstly constructs an n×n matrix of the sum of each gender’s preference of the other gender Pij. It then selects the minimum sum preference minPij in the constructed matrix and deletes its corresponding row i and column j. This process is repeated until i=0 ∩ j=0, after which the algorithm compares initially or last chosen minPij its alternatives to finally determine one that yields the maximum marginal increase in preference. When applied to 7 stable marriage problems, the proposed algorithm has improved on initial solutions of existing algorithms.

한국어

본 논문은 안정된 결혼문제의 최적 해를 쉽고 빠르게 찾는 알고리즘을 제안하였다. 첫 번째로, 남성의 여성 선호도와 여성의 남성 선호도 합 Pij 의 n×n 정방행렬 할당문제로 변환시킨다. 두 번째로, 행렬에서 최대 선호도 합 (최소 값)인 minPij를 선택하고 i행과 j열을 삭제한다. 이 과정을 i=0 ∩ j=0 일 때까지 수행한다. 세 번 째로, 가능한 최초 또는 마지막 선택 minPij에 대해 다른 값으로 변경시 선호도를 증가시킬 수 있으면 상호 교환하는 검증 절차 를 수행한다. 제안된 알고리즘을 7개의 안정된 결혼문제에 적용한 결과 기존 알고리즘의 해를 개선하는 효과를 얻었다.