SORT 논문을 학습중에 헝가리안 알고리즘이란 것을 쓴다는데... 도대체 이건 또 뭔지 알아보려고합니다..
Hungarian Algorithm이란?
헝가리안 알고리즘이라는 것은 assignment problem을 해결하는 최적의 솔루션(optimal solution) 입니다.
그럼 먼저 assignment problem이 뭔지?,
그리고 어떻게 헝가리안 알고리즘이 사용하는지?
알아보겠습니다.
assignment problem이란?
직역하면 할당 문제입니다.
어떻게 하면 가장 효과적으로 할당할 것이냐의 문제인데,
예를 들면, 회사에서 외주를 맡겨야 할 일이 3개가 있다고 한다면(식당, 보안, 환경관리)
해당 일들을 3개의 업체에 맡겨야 하는데 어떻게 맡기는것이 가장 효과적인가 하는 문제입니다.
아래는 각 업체별 업무에 따른 가격이 나와있습니다.
| 가격 |
식당 |
보안관리 |
환경관리 |
| A업체 |
4 |
7 |
3 |
| B업체 |
5 |
6 |
1 |
| C업체 |
2 |
5 |
3 |
Optimal Solution (Hungarian algorithm)
위와 같은 상황에서 어떻게 하면 회사는 가장 저렴한 가격으로 각각의 업무를 부여할 수 있을까요?
이것을 해결하는 방법은 다음과 같은 절차를 따릅니다.
1. 행에 대해서 가장 작은 값으로 뺀다
-> 이 이유는 A업체에 각각에 비용에 3을 빼더라도 환경관리가 가장 싸고, 보안관리가 가장 비싸다는 내용 자체의 변화는 없기 때문입니다. 동일하게 행에 해당하는 B,C 업체도 동일하게 진행해줍니다.
가격
|
식당
|
보안관리
|
환경관리
|
|
A업체
|
1 |
4 |
0 |
3 |
B업체
|
4 |
5 |
0 |
1 |
C업체
|
1 |
3 |
0 |
2 |
2. 열에 대해서 가장 작은값으로 뺀다.
이유는 동일합니다. 식당일은 1을 빼더라도 A,C업체가 가장 싸고 B업체가 비싼것에는 차이가 없기 때문입니다.
가격
|
식당
|
보안관리
|
환경관리
|
|
A업체
|
0 |
1 |
0 |
3 |
B업체
|
3 |
2 |
0 |
1 |
C업체
|
0 |
0 |
0 |
2 |
| |
1 |
3 |
0 |
|
이렇게 얻은 행렬에서 0의 값을 가지는 업체-업무 쌍만 알게된다면 가장적은 비용으로 모든 업무를 처리해 낼 수 있을것입니다. 단 여기서 값에 해당하는 모든 행과 열은 0 이상의 값이여야 최적화를 할 수 있습니다.
3. 모두가 0이되는 행과 열을(minimum-size vertex cover) 제외하고 가장 작은 값을 찾아 모든 행에 빼줍니다.
가격
|
식당
|
보안관리
|
환경관리
|
|
A업체
|
-1 |
0 |
-1 |
3+1 |
B업체
|
2 |
1 |
-1 |
1+1 |
C업체
|
0 |
0 |
0 |
2 |
| |
1 |
3 |
0 |
|
4. 음수가 되는 행렬의 원소를 음이 아닌수로 만들어 줍니다.
| |
식당
|
보안관리
|
환경관리
|
|
A업체
|
0 |
0 |
0 |
3+1 |
B업체
|
3 |
1 |
0 |
1+1 |
C업체
|
1 |
0 |
1 |
2 |
| |
0 |
3 |
-1 |
|
최종적으로 A업체 - 식당, B업체 - 환경관리, C업체 - 보안관리가 최적의 선택이라는 결과가 나옵니다.
| 가격 |
식당 |
보안관리 |
환경관리 |
| A업체 |
4 |
7 |
3 |
| B업체 |
5 |
6 |
1 |
| C업체 |
2 |
5 |
3 |
이 같은 알고리즘이 바로 헝가리안 알고리즘입니다.
헝가리안 알고리즘
1. 각 행에서 가장 작은 항목을 해당 행의 다른 모든 항목에서 뺍니다. 이렇게 하면 행의 가장 작은 항목이 0이 되게 됩니다.
2. 각 열에서 가장 작은 항목을 해당 열의 다른 모든 항목에서 뺍니다. 이렇게 하면 열의 가장 작은 항목이 0이 되게 됩니다.
3. 0 항목을 포함하는 행과 열을 표시하여 가능한 적은 수의 선을 그립니다.
4. 만약 그려진 선이 n개라면, 0의 최적 할당이 가능하며 알고리즘이 완료됩니다. 선의 수가 n보다 적으면, 최적 수의 0이 아직 달성되지 않았습니다. 다음 단계로 이동합니다. (여기서 n은 행의수 = 열의수 = n)
5. 어떠한 선으로도 커버되지 않은 가장 작은 항목을 찾습니다. 이 항목을 선이 그어지지 않은 각 행에서 빼고, 선이 그려진 각 열에서 더합니다. 그런 다음, 단계 3으로 돌아갑니다. |
reference
https://gazelle-and-cs.tistory.com/29
