- 할당 문제의 최적 알고리즘
- ㆍ 저자명
- 이상운,Lee. Sang-Un
- ㆍ 간행물명
- 韓國컴퓨터情報學會論文誌
- ㆍ 권/호정보
- 2012년|17권 9호|pp.139-147 (9 pages)
- ㆍ 발행정보
- 한국컴퓨터정보학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
본 논문에서는 할당 문제의 최적해를 간단히 찾을 수 있는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계 수행 과정을 1단계로 단축시켰으며, 행과 열의 최소 비용만을 선택하여 비용을 감소시키는 최적화 과정을 거쳐 최적해를 구하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 유전자 알고리즘으로 찾지 못한 최적해를 찾는데 성공하였다. 제안된 알고리즘은 Hungarian 알고리즘의 수행 복잡도 O($n^3$)을 O(n)으로 향상시켰다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체하여 할당 문제에 일반적으로 적용할 수 있는 알고리즘으로 널리 활용될 수 있을 것이다.
This paper suggests simple search algorithm for optimal solution in assignment problem. Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm. The proposed algorithm reduces the 4 steps of Hungarian algorithm to 1 step, and only selects the minimum cost of row and column then gets the optimal solution simply. For the 27 balanced and 7 unbalanced assignment problems, this algorithm finds the optimal solution but the genetic algorithm fails to find this values. This algorithm improves the time complexity O($n^3$) of Hungarian algorithm to O(n). Therefore, the proposed algorithm can be general algorithm for assignment problem replace Hungarian algorithm.