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

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

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

기타언어초록

본 논문은 할당 문제의 최적해를 간단히 찾을 수 있는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계 수행 과정을 2단계로 단축시켰다. 첫 번째로, 행렬의 최소 비용을 선택하고 행과 열의 값을 삭제하는 과정을 거쳐 초기 할당을 수행하였다. 두 번째로 할당을 조정하는 과정을 수행하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 Genetic 알고리즘으로 찾지 못한 최적해를 찾는데 성공하였다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체하여 일반적으로 적용할 수 있을 것이다.

기타언어초록

This paper proposes an algorithm that seeks the optimal solution for an assignment problem through a simplified process. Generally it is Hungarian algorithm that is prevalently used to solve a given assignment problem. The proposed algorithm reduces 4 steps Hungarian algorithm into 2 steps. Firstly, the algorithm selects the minimum cost from a matrix and deletes the rest of the rows and columns. Secondly, it improves on the solution through reassignment process. For 27 balanced assignment problems and 7 unbalanced problems, the proposed algorithm has successfully yielded the optimal solution, which Genetic algorithm has failed. This algorithm is thus found to be an appropriate replacement of Hungarian algorithm.