헝가리안 알고리즘 (Hungarian Algorithm)

할당 문제를 해결하기 위한 헝가리안 알고리즘. 

할당 문제란 일대일 대응을 만드는 것과 비슷하다. 예를들어 사람의 그룹 A가 있고 A 그룹에 속하는 사람들이 각각 업무를 하나씩 배정 받는다고 가정하자. 이때, 업무의 수는 그룹 A에 속하는 사람 수와 같고 그룹 A에 모든 사람은 빠짐 없이 업무를 1개씩 배정 받는다. 이때 각 사람은 적성이 존재하기 때문에 업무에 따라 효율이 다르다고 하면 그룹 A의 속하는 모든 사람의 업무 효율이 최대가 되도록 업무를 배정하는 경우를 구해야 된다고 하자. 

 

위와 같은 문제를 풀 때, 모든 경우의 수는 (A그룹의 사람수)! 이다. 업무를 줄 세우는 방법과 같으므로 팩토리얼이 사용된다. 그러나 팩토리얼의 경우 연산량이 어마어마하다. O(n)과 O(n^2) 같은 다항식보다 훨씬 크고 심지어 O(2^n)과 같은 지수 함수보다 Time Compexity가 높은 O(n!)이다. 

따라서 위와 같은 알고리즘 보다 훨씬 효율적인 알고리즘이 필요했고 이를 헝가리안 알고리즘이라고 한다.