earticle

논문검색

할당 문제의 단순한 해법

원문정보

AThe Simplified Solution for Assignment Problem

이상운

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

This paper suggests more simple algorithm than Hungarian algorithm for assignment problem. Hungarian algorithm selects minimum cost of row and column, and subtracts minimum cost from each cost. Then, performs until the number of minimum lines with 0 equals the number of rows. But, the proposed algorithm selects the minimum cost for each rows only. From the start point with over 2 to the target point with null selects in column, fixes the maximum opportunity cost that the difference of the cost of starting point and target point, and moves the cost less than opportunity cost th more than previous cost. For the 25 balance and 7 unbalance assignment problems, This algorithm gets the optimal solution same as Hungarian algorithm. This algorithm improves the time complexity O(n3) of Hungarian algorithm to O(n2), and do not performs the transformation process from unbalance to balance assignment in Hungarian algorithm. Therefore, this algorithm can be alter Hungarian algorithm in assignment problem.

한국어

본 논문은 할당 문제의 최적해를 찾는 대표적인 Hungarian 보다 간단히 최적해를 구하는 알고리즘을 제안하 였다. Hungarian 알고리즘은 행과 열의 최소 비용을 선택하고 각 비용에서 최소 비용을 뺀다. 다음으로 0을 모두 포 함하는 최소한의 선이 행의 개수 가 될 때까지 수행한다. 반면에 제안된 알고리즘은 단지 행에 대해 최소 비용을 선 택한다. 다음으로 열에 대해 2개 이상 선택된 열을 출발지로, 하나도 선택되지 않은 열을 목적지로하여 출발지의 비 용에서 목적지의 최소 비용과의 차이인 기회비용이 가장 큰 비용은 고정시키고 기회비용이 보다 작은 비용들을 다음 으로 큰 비용으로 이동시키는 방법을 적용하였다. 제안된 방법을 25개의 균형 할당과 7개의 불균형 할당 문제에 적용 하여 Hungarian 알고리즘과 동일한 최적해를 구하는데 성공하였다. 제안된 알고리즘은 Hungarian 알고리즘의 수행 복 잡도 O(n3) 를 O(n2)로 개선하였으며, 불균형을 균형 할당 문제로 변환시키는 과정도 수행하지 않는 단순한 알고리즘 이다. 따라서 할당 문제의 Hungarian 알고리즘을 대체시킬 수 있을 것이다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 관련 연구와 연구 배경
 Ⅲ. 단순 할당 알고리즘
 Ⅳ. 알고리즘 적용성 평가
  1. 균형 할당 문제
  2. 불균형 할당 문제
  3. 알고리즘 성능 평가
 Ⅳ. 결론 및 향후 연구과제
 참고문헌

저자정보

  • 이상운 Sang-Un, Lee. 정회원, 강릉원주대학교 과학기술대학 멸티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,200원

      0개의 논문이 장바구니에 담겼습니다.