Munkres 알고리즘

배정(assignment) 문제를 해결하기 위한 알고리즘입니다.

 

Munkres 알고리즘의 핵심은 비용 행렬에서 같은 행 또는 같은 열에 있는 요소들에 대해

같은 값을 더하거나 빼는 것으로 비용 행렬의 일부를 변형하는 것입니다.

 

비용 그 자체를 구하는게 아니라 최소 또는 최대의 값을 구하는 것이기 때문에 가능한 연산입니다.

Munkres 알고리즘의 입력은 2차원 행렬입니다.

출력은 배정의 최소 비용 및 매칭 정보(어느 행과 어느 열이 매칭되었는지)입니다.

 

배정 문제 또는 본 알고리즘에 입력되는 입력에 관한 정보는 이전 글을 참고해주시기 바랍니다.

배정(Assignment) 문제 (tistory.com)

배정(Assignment) 문제

 

Step0: n*m 비용 행렬을 정합니다.

Step1: 각각의 행 별로 진행합니다.

행에 있는 모든 요소에 그 행의 요소 중 최소인 값을 뺍니다.

Step2: Step1의 결과가 최종 결과인지 확인합니다. 마지막 열이 결정되지 않으므로

이번에는 각각의 열 별로 진행합니다.

열에 있는 모든 요소에 그 열의 요소 중 최소인 값을 뺍니다.

 

최종 결과를 확인하는 방법은 행렬에 선을 그어보면 알 수 있습니다.

모든 0을 포함하는 최소 개수의 선을 행렬에 긋습니다.

이 때, 모든 행이나 열이 선으로 채워지면 최종 결과로 선택할 수 있습니다.

 

그어지지 않은 행이 있기 때문에 최종 결과가 아닙니다.

 

Step3: 선이 그어지지 않은 요소 중 최소값으로 Step1을 진행합니다.

단, 선이 그어지지 않은 행에만 적용합니다.

2행과 3행이 선이 그어지지 않았으므로

2행, 3행에 최소값인 1을 빼서 적용시켰습니다.

음수가 있는 열은 모든 열에 최소값을 다시 더하여 음수를 없앨 수 있습니다.

다시 step2의 과정으로 선을 그으면

0을 포함하게 그을 수 있는 선의 개수가 3개로 최적의 값을 구했습니다.

0이 1개인 행부터 요소를 찾아나가면 최소 비용의 매칭을 확인 할 수 있습니다.