배정(Assignment) 문제

이 문제의 자료 구조는 이분 그래프(bipartite graph)입니다.

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

두 그룹으로 나눌 수 있고,

같은 그룹 내에서 연결되는 간선이 없습니다.

그리고 작업 하나 당 모든 작업자와 연결되는 완전 연결(fully connected) 형태입니다.

 

가장 대표적인 예시가

작업과 작업자 간의 할당입니다.

작업 1,2,3과 작업자 A,B,C 간에 가장 적은 비용으로 매칭시키는 방법을 찾는 예시입니다.

 

좌측의 노드를 작업으로, 우측의 노드가 작업자로 그래프를 구성할 수 있습니다.

각 작업들은 모든 작업자와의 간선을 가지고 있고 간선의 가중치가 비용이 됩니다.

그래프는 행렬로 나타내면 알고리즘을 적용시킬 수 있는 형태의 데이터가 됩니다.

위 그림에서는 행이 작업이고, 열이 작업자가 됩니다.

생성한 행렬의 각 요소는 행과 열 간의 비용입니다.

 

이 배정 문제의 결과는 최소 비용으로 두 그룹을 이어주는 간선들을 찾는 것입니다.

찾은 간선들이 연결하는 노드는 중복되면 안됩니다.(행이나 열이 중복되면 안됩니다.)

 

배정 문제를 해결하는 방법 중 대표적인 알고리즘이 헝가리안 알고리즘입니다.

Munkres 알고리즘이라고도 합니다.

 

헝가리안 알고리즘

Munkres 알고리즘 (tistory.com)

Munkres 알고리즘

https://github.com/mcximing/hungarian-algorithm-cpp 

GitHub - mcximing/hungarian-algorithm-cpp: A C++ wrapper for a hungarian algorithm implementation

Munkres global nearest neighbor assignment algorithm - MATLAB assignmunkres - MathWorks 한국

Munkres global nearest neighbor assignment algorithm - MATLAB assignmunkres - MathWorks 한국

(PDF) Tutorial on Implementation of Munkres' Assignment Algorithm (researchgate.net)

(PDF) Tutorial on Implementation of Munkres' Assignment Algorithm