Abstract
Generally, the stable marriage problem can be applied Gale-Shapley algorithm with $O(|V|^2|E|)$ time complexity. This algorithm has a complex and can be fail to obtain optimal solution. This paper proposes an algorithm that effortlessly and expeditiously obtains the optimal solution for 2 marriage problems with or without weight. The algorithm for the Minimum-weight matching problem by formulating square matrix of $n{\times}n$, which is the sum of men's female preference and women's male preference. To solve the given problem, the algorithm determines the minimum value from rows and columns, selects single cells. Also, it derives an initial solution for cells whose column and row have not been selected. In a case where initial solution fails to obtain the minimum value from both row and column, the algorithm carries out solution-improvement it is moved to the row's minimum value. For the Maximum matching problem, this proposed algorithm readily obtains the solution by selecting an edge of a vertex whose degree=1, and by deleting an unselected edge among incident edges of the two vertices connected by a common edge. When applied to 6 Minimum-weight matching problems and 7 Maximum matching problems, the proposed algorithm has obtained solutions superior to those obtained by the existing algorithms. This algorithm has a merit of readily and rapidly obtaining the solution in linear time complexity $O(|V|)$, and thus could as well be utilized to obtain the optimal solution for Marriage problem.
결혼문제는 일반적으로 수행 복잡도가 $O(|V|^2|E|)$인 Gale-Shapley 알고리즘을 적용하고 있다. 이 알고리즘은 복잡할 뿐 아니라 안정된 결혼 최적해를 찾지 못할 수도 있다. 본 논문은 가중치가 있거나 없는 2가지 결혼문제의 최적해를 쉽고 빠르게 찾는 알고리즘을 제안하였다. 최소 가중치 매칭 결혼문제는 남성의 여성 선호도와 여성의 남성 선호도의 합을 갖는 $n{\times}n$ 정방행렬의 해를 구하는 방법을 적용하였다. 이 문제는 행과 열의 최소값을 결정하고 1개씩만 선택된 셀을 선택하였다. 또한, 행과 열이 선택되지 않은 셀을 선택하여 초기해를 구하였다. 만약, 초기해가 행과 열 모두에서 최소값을 갖지 않은 경우 행을 기준으로 행렬 최소값으로 해개선 작업을 수행하였다. 최대 매칭 결혼문제는 차수가 1인 정점의 간선을 선택하고 선택된 간선의 양 끝단 정점에 부속된 간선들 중 선택되지 않은 간선을 삭제하는 방법으로 쉽게 해를 구하였다. 제안된 알고리즘을 6개의 최소 가중치 매칭 결혼문제와 7개의 최대 매칭 결혼문제에 적용한 결과 기존 알고리즘으로 얻은 해를 개선하는 효과를 얻었다. 본 알고리즘은 선형시간 복잡도 $O(|V|)$로 쉽고 빠르게 해를 얻는 장점을 갖고 있어 결혼문제의 최적해를 얻는 방법으로 활용될 수 있을 것이다.