할당 문제

할당 문제(Assignment Problem)란?

할당(배정) 문제는 기계를 태스크에, 일꾼을 작업에, 축구 선수를 포지션에 할당하는 것이다. 목표는 효율성이 최대가 되거나 총비용이 최소가 되는 최적의 할당 방법을 결정하는 것이다.

아래 그림과 같이 4명의 일꾼과 4개의 작업이 있다.

J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23

4 명의 일꾼들이 4 개의 작업을 처리하는 시간들을 나타내는 표이다. 한명의 일꾼이 하나의 작업을 수행 할 수 있다. 모든 작업을 수행하기 위해 필요한 총 시간을 최소로 하고 싶다

최적해는 (일꾼, 작업) (1, 3), (2, 2) , (3, 1), (4,4) 총 시간은 140이다.

헝가리안 알고리즘으로 이 최적 할당을 찾을 수 있다.

헝가리안 알고리즘의 실행 과정

> n x n 배열(행렬)

  1. 각 행에 대해서, 최소값을 찾아서 행의 모두 요소의 값에서 뺀다.
  2. 각 열에 대해서, 최소값을 찾아서 열의 모는 요소의 값에서 뺀다.
  3. 최소 개수의 직선(line)으로 0을 지운다(커버한다.) 만약, n개의 직선이 필요하다면, 최적의 할당은 0값들 중에 존재한다. 알고리즘을 종료한다.만약, n보다 적은 수라면, 4단계를 수행한다.
  4. 추가적인 0을 생성한다. 직선으로 커버되지 않은 최소값(k)을 찾아서 커버되지 않은 모든 값들에서 최소값(k)을 뺀다. 두 번 커버된 모든 값들에 최소값(k)을 더한다.

더 보기

참고> www.hungarianalgorithm.com