While studying the SORT paper, I came across the term "Hungarian Algorithm." I had no idea what it was, so I decided to look into it.
What Is the Hungarian Algorithm?
The Hungarian Algorithm is an optimal solution to the assignment problem.
Before diving into how the algorithm works, let's first understand what the assignment problem is and why the Hungarian Algorithm is used to solve it.
What Is the Assignment Problem?
The assignment problem deals with how to assign tasks in the most efficient way possible.
For example, suppose a company has three tasks that need to be outsourced: restaurant services, security management, and environmental management. There are also three different service providers available. The goal is to assign each task to a provider in a way that minimizes costs.
Below is a cost matrix representing the price each provider charges for each task:
CostRestaurantSecurityEnvironment
| Company A | 4 | 7 | 3 |
| Company B | 5 | 6 | 1 |
| Company C | 2 | 5 | 3 |
Finding the Optimal Solution (Hungarian Algorithm)
How can the company assign these tasks at the lowest possible cost? The Hungarian Algorithm follows these steps to solve the problem:
Step 1: Subtract the minimum value from each row
- In each row, subtract the smallest value from all elements in that row.
- This keeps the relative cost structure intact while introducing zeros.
CostRestaurantSecurityEnvironment
| Company A | 1 | 4 | 0 |
| Company B | 4 | 5 | 0 |
| Company C | 1 | 3 | 0 |
Step 2: Subtract the minimum value from each column
- In each column, subtract the smallest value from all elements in that column.
- This further simplifies the matrix without changing the cost relationships.
CostRestaurantSecurityEnvironment
| Company A | 0 | 1 | 0 |
| Company B | 3 | 2 | 0 |
| Company C | 0 | 0 | 0 |
Now, if we can find an assignment where each task is assigned using only zero-cost cells, we have our optimal solution.
Step 3: Cover all zeros using the minimum number of lines
- Draw the minimum number of lines required to cover all zeros in the matrix.
- If the number of lines equals the matrix size (n × n), an optimal solution exists. If not, proceed to the next step.
CostRestaurantSecurityEnvironment
| Company A | -1 | 0 | -1 |
| Company B | 2 | 1 | -1 |
| Company C | 0 | 0 | 0 |
Step 4: Adjust the remaining values
- Find the smallest uncovered value. Subtract it from all uncovered elements and add it to elements where two lines overlap.
CostRestaurantSecurityEnvironment
| Company A | 0 | 0 | 0 |
| Company B | 3 | 1 | 0 |
| Company C | 1 | 0 | 1 |
Final Assignment
By following the Hungarian Algorithm, the optimal assignment is:
- Company A → Restaurant
- Company B → Environment
- Company C → Security
CostRestaurantSecurityEnvironment
| Company A | 4 | 7 | 3 |
| Company B | 5 | 6 | 1 |
| Company C | 2 | 5 | 3 |
This is the essence of the Hungarian Algorithm!
Hungarian Algorithm Summary
- Subtract the smallest value in each row from all elements in that row.
- Subtract the smallest value in each column from all elements in that column.
- Cover all zeros with the minimum number of lines.
- If the number of lines equals n, an optimal assignment exists. Otherwise, proceed to step 5.
- Find the smallest uncovered value, subtract it from uncovered elements, and add it to elements at line intersections. Then, repeat step 3.
'프로그래밍 > 수학' 카테고리의 다른 글
| What is a Vertex Cover? (0) | 2025.03.18 |
|---|---|
| What is the Natural Constant e (Exponential)? (0) | 2025.03.15 |
| Likelihood와 최대우도추정(MLE): 확률과 데이터의 관계 쉽게 이해하기 (1) | 2024.10.04 |
| 조건부 종속성(Conditional Dependence)이란? 쉽게 이해해보기 (3) | 2024.10.03 |
| 확률 변수 & 확률 함수 (5) | 2024.09.30 |