헝가리 방법 : 구성 요소, 예 - DUDAS - 2026

헝가리어 방법은 당신이 비용을 최소화하고자 할 때 할당 문제에 사용되는 알고리즘이다. 즉, 최소 비용을 기준으로 다양한 활동에 여러 사람을 배정하여 최소 비용을 찾는 데 사용됩니다. 각 활동은 다른 사람에게 할당되어야합니다.

할당 문제는 특별한 유형의 선형 계획법 문제로, 목표는 여러 사람이 여러 작업을 완료하는 데 드는 비용이나 시간을 최소화하는 것입니다.

출처 : pixabay.com

할당 문제의 중요한 특징 중 하나는 기계 (또는 프로젝트)에 하나의 작업 (또는 작업자) 만 할당된다는 것입니다.

이 방법은 헝가리 수학자 D. Konig에 의해 개발되었습니다. 이러한 이유로 할당 문제에 대한 헝가리 방법으로 알려져 있습니다. Kuhn-Munkres 할당 알고리즘이라고도합니다.

모든 할당 문제는 두 단계로 구성된이 방법을 적용하여 쉽게 해결할 수 있습니다.

-첫 번째 단계에서는 행 축소 및 열 축소가 수행됩니다.

-두 번째 단계에서는 솔루션이 반복적으로 최적화됩니다.

헝가리 식 방법은 무엇입니까?

헝가리어 방법은 4 단계로 구성됩니다. 처음 두 단계는 한 번만 실행되는 반면 3 단계와 4 단계는 최적의 할당을 찾을 때까지 반복됩니다.

n x n 차의 정사각형 행렬은 음이 아닌 요소 만 포함해야하는 입력 데이터로 간주됩니다.

주어진 문제에 대해 행렬의 행 수가 열 수와 같지 않으면 경우에 따라 더미 행 또는 더미 열을 추가해야합니다. 이러한 더미 셀의 할당 비용은 항상 0으로 할당됩니다.

1 단계 : 각 행의 최소값 빼기

배열의 각 행에 대해 가장 낮은 값을 가진 요소가 선택되고 해당 행의 각 요소에서 뺍니다.

2 단계 : 각 열에서 최소값 빼기

마찬가지로 값이 가장 낮은 항목이 각 열에 대해 선택되고 해당 열의 각 항목에서 뺍니다.

3 단계 : 최소 줄 수로 모든 0을 덮습니다.

2 단계에서 생성 된 행렬의 모든 0은 행 또는 열로 최소한의 가로 및 세로 선을 사용하여 가려 져야합니다.

모든 0을 처리하기 위해 총 n 개의 라인이 필요한 경우 (n은 행렬의 n x n 크기와 같음) 0 사이에 최적의 할당이 이루어 지므로 알고리즘이 중지됩니다.

그렇지 않고 어레이의 모든 0을 처리하는 데 n 줄 미만이 필요한 경우 4 단계로 진행합니다.

4 단계 : 추가 0 생성

3 단계에서 만든 선 중 하나에 포함되지 않는 행렬의 가장 작은 요소 (k라고 함)가 선택됩니다.

k 값은 선으로 덮이지 않는 모든 요소에서 뺍니다. 결과적으로 ka의 값은 두 선의 교차점에 포함되는 모든 요소에 추가됩니다.

한 줄로 표시된 항목은 그대로 유지됩니다. 이 단계를 수행 한 후 3 단계로 돌아갑니다.

최적의 할당

알고리즘이 3 단계에서 중지 된 후 각 행과 각 열에 하나의 0 만 선택되도록 0 세트가 선택됩니다.

이 선택 프로세스에서 행이나 열에 단일 0이 없으면 해당 0 중 하나가 선택됩니다. 해당 열 또는 행의 나머지 0은 제거되고 다른 할당에 대해서도 동일하게 반복됩니다.

단일 제로 할당이 없으면 여러 솔루션이 있습니다. 그러나 비용은 다른 할당 세트에 대해 동일하게 유지됩니다.

추가 된 모든 더미 행 또는 열이 제거됩니다. 따라서이 최종 행렬에서 선택한 0은 원래 행렬에 필요한 이상적인 할당에 해당합니다.

예

4 명의 작업자 (T1, T2, T3, T4)가 수행해야하는 4 가지 활동 (A1, A2, A3, A4)이있는 회사를 가정 해 보겠습니다. 작업 자당 하나의 활동이 지정되어야합니다.

다음 매트릭스는 특정 작업자를 특정 활동에 할당하는 비용을 보여줍니다. 목표는이 네 가지 활동으로 구성된 작업의 총 비용을 최소화하는 것입니다.

1 단계 : 각 행의 최소값 빼기

해당 행의 다른 요소에서 각 행의 최소값을 가진 요소를 빼서 시작합니다. 예를 들어, 첫 번째 행의 가장 작은 요소는 69입니다. 따라서 첫 번째 행의 각 요소에서 69를 뺍니다. 결과 행렬은 다음과 같습니다.

2 단계 : 각 열에서 최소값 빼기

같은 방법으로 각 열의 최소값을 가진 요소를 해당 열의 다른 요소에서 빼서 다음 행렬을 얻습니다.

3 단계 : 최소 줄 수로 모든 0을 덮습니다.

이제 행렬의 모든 0을 포함하는 데 필요한 최소 줄 수 (가로 또는 세로)를 결정합니다. 모든 0은 다음 3 줄을 사용하여 다룰 수 있습니다.

필요한 줄 수가 3 개이고 행렬 크기 (n = 4)보다 작으므로 4 단계를 계속합니다.

4 단계 : 추가 0 생성

값이 6 인 선으로 덮이지 않는 가장 작은 요소가 선택됩니다.이 값은 덮이지 않은 모든 요소에서 빼고이 동일한 값이 두 선의 교차점에 포함 된 모든 요소에 더해집니다. 결과적으로 다음과 같은 매트릭스가 생성됩니다.

헝가리어 방법에 표시된대로 3 단계를 다시 수행해야합니다.

3 단계 (반복)

다시 행렬의 모든 0을 덮는 데 필요한 최소 줄 수가 결정됩니다. 이번에는 네 줄이 필요합니다.

필요한 라인의 수가 행렬의 크기 (n = 4)와 같은 4 개이므로 행렬의 0 사이에 최적의 할당이 있습니다. 따라서 알고리즘이 중지됩니다.

최적의 할당

방법에서 알 수 있듯이 다음 0을 선택하면 최적 할당에 해당합니다.

이 0의 선택은 원래 비용 매트릭스에서 다음과 같은 최적 할당에 해당합니다.

따라서 작업자 1은 활동 3, 작업자 2, 활동 2, 작업자 3, 활동 1 및 작업자 4는 활동 4를 수행해야합니다.이 최적 할당의 총 비용은 69 + 37 +입니다. 11 + 23 = 140.

참고 문헌

1. 헝가리 알고리즘 (2019). 헝가리 알고리즘. 출처 : hungarianalgorithm.com.
2. 연구 (2019). 헝가리 알고리즘을 사용하여 과제 문제 해결. 출처 : study.com.
3. Wisdom Jobs (2018). 할당 문제를 해결하기위한 헝가리 방법-관리를위한 정량적 기법. 출처 : wisdomjobs.com.
4. Geeks for Geeks (2019). 할당 문제에 대한 헝가리 알고리즘. 출처 : geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). 헝가리어 최대 일치 알고리즘. 훌륭한. 출처 : brilliant.org.