헝가리안 할당(최소 비용 배정) 계산기

사람마다 일마다 비용이 정해져 있을 때, 한 사람에 한 일씩 겹치지 않게 배정하되 총비용이 가장 작아지는 조합을 찾는 문제입니다. 사람과 일, 기계와 작업, 배송기사와 구역처럼 일대일로 붙여야 하는 배정이 모두 여기에 해당합니다.

안 됩니다. 여러 사람이 같은 일을 제일 싸게 할 수 있으면 열이 겹쳐 배정 자체가 성립하지 않습니다. 그렇게 고른 합은 도달할 수 없는 값이고, 실제 최소는 그보다 큽니다. 이 도구는 두 값을 나란히 보여 줍니다.

행이나 열 전체에서 같은 수를 빼도 최적 배정이 바뀌지 않는다는 성질을 씁니다. 어느 배정이든 그 행에서 정확히 하나를 고르므로 모든 배정의 총합이 똑같이 줄어들어 순위가 그대로이기 때문입니다. 그래서 최솟값을 빼 0을 만들어 나가다가 0만으로 배정을 완성할 수 있게 되면 그것이 최적입니다.

n명이면 n!가지라 금방 손을 뗍니다. 10명이면 362만 가지, 12명이면 4억 8천만 가지가 넘습니다. 헝가리안 알고리즘은 인원의 세제곱에 끝나므로 12명이라도 즉시 나옵니다.

부호를 뒤집으면 최소화 문제가 되어 같은 알고리즘을 그대로 씁니다. 이 도구는 위에서 「이익 최대」를 고르면 알아서 바꿔 계산합니다.

모자란 쪽에 비용 0짜리 가짜 줄을 덧대 정사각형으로 만들어 풉니다. 가짜에 배정된 것은 「그 사람은 아무 일도 맡지 않는다」 또는 「그 일은 아무도 맡지 않는다」는 뜻이라, 결과에서 빼고 누가 남는지 따로 알려 줍니다.

셋 다 배정 문제지만 목적이 다릅니다. 이분 매칭은 비용 없이 짝의 «개수»만 최대로 하고, 안정 매칭은 선호 «순위»로 불안정한 쌍이 없게 만들며, 할당 문제는 «비용의 합»을 최소로 합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.