기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
할당 문제의 단순한 해법
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 할당 문제의 단순한 해법
저자명
이상운,Lee. Sang-Un
간행물명
한국인터넷방송통신학회 논문지
권/호정보
2012년|12권 5호|pp.141-151 (11 pages)
발행정보
한국인터넷방송통신학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

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

기타언어초록

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(n^3)$ of Hungarian algorithm to $O(n^2)$, 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.