Hungarian algorithm
Welzl`s algorithm에 이어 플러그인에서 에이전트의 위치 할당을 하기 위해 사용한 알고리즘인 Hungarian algorithm에 대해서도 이해를 위해 글을 통해 정리한다.
최적 할당 문제
최적 할당 문제는 여러 작업을 여러 작업자(또는 기계, 자원)에 배정할 때, 전체 비용을 최소화하거나 이익을 최대화하도록 배정 방법을 찾는 문제를 의미한다. 대표적인 예시를 들면 다음과 같은 상황이 있다.
- n개의 작업과 n명의 작업자가 있는 상황.
- 작업자 i가 작업 j를 수행할 때 드는 비용 가 주어진다.
- 각 작업에 정확히 한 명의 작업자를 배정하고, 각 작업자는 정확히 하나의 작업만 맡도록 하면서 총 비용 ∑ 가 최소가 되도록 하는 할당 방법을 찾는다.
이 문제는 cost matrix가 주어졌을 때, 한 행과 한 열에서 각각 하나씩 선택해 전체 합을 최소화하는 문제와 동치로, 완전 이분 그래프에서 최소 가중치 완전 매칭을 찾는 문제로 볼 수 있다.
Hungarian algorithm
헝가리안 알고리즘은 최적 할당 문제를 시간 복잡도로 구하는 알고리즘으로 cost matrix에 다음과 같은 동작을 수행하는 방식으로 작동한다.
- 행 최소값 빼기
- 각 행에서 최소값을 그 행 전체에서 빼서, 적어도 하나의 0가 있도록 만든다.
- 이 연산은 모든 배정에 대해 비용을 동일하게 감소시키므로, 최적해의 상대적 구조는 변하지 않는다.
- 열 최소값 빼기
- 각 열에서도 최소값을 빼서, 각 열에도 적어도 하나의 0가 존재하도록 만든다.
- 마찬가지로 최적 해의 상대적인 비용 비교는 그대로 유지된다.
- 0이된 값들을 이용해 가능한 매칭 찾기
- 0이 있는 칸들만 이용해서, 서로 다른 행과 열에서 0을 하나씩을 선택해 최대한 많은 매칭을 만든다.
- 만약 n개의 0를 선택해 완전 매칭을 만들 수 있다면, 그 매칭이 바로 최적 해가 된다.
- 완전 매칭이 안 되면 행/열 조정
- 모든 0를 최소 개수의 일부 행과 일부 열을 선택하여 덮는 과정을 수행하고, 덮이지 않은 칸들 중 가장 작은 값을 찾아, 덮이지 않은 모든 칸에서 그 값을 빼고, 교차하는 두 직선이 만나는 칸에는 그 값을 더한다. 이를 통해 새로운 0인 칸이 생기면서 최적성이 유지되며, 다시 매칭을 시도할 수 있다.
- 완전 매칭이 가능해질 때까지 3–4 반복
- 이 과정을 반복하면 언젠가 0들만으로 완전 매칭을 찾을 수 있고, 그 매칭이 원래 비용 행렬에서의 최적 할당이 된다.
아래는 3x3비용 행렬을 기준으로 하는 알고리즘 동작 예시이다.
아래와 같은 비용 행렬이 있다고 하면,
| 작업자 \ 작업 | 작업 1 | 작업 2 | 작업 3 |
|---|---|---|---|
| 작업자 1 | 4 | 1 | 3 |
| 작업자 2 | 2 | 0 | 5 |
| 작업자 3 | 3 | 2 | 2 |
각 행의 최소값은 순서대로 1, 0, 2이므로, 이를 각 행에서 빼면 다음과 같은 행렬이 된다.
| 작업자 \ 작업 | 작업 1 | 작업 2 | 작업 3 |
|---|---|---|---|
| 작업자 1 | 3 | 0 | 2 |
| 작업자 2 | 2 | 0 | 5 |
| 작업자 3 | 1 | 0 | 0 |
이제 각 행마다 최소 하나 이상의 0이 존재하게 된다. 이제 열을 기준으로도 최소값을 빼주는 작업을 시행하면 다음과 같이 변경된다.
| 작업자 \ 작업 | 작업 1 | 작업 2 | 작업 3 |
|---|---|---|---|
| 작업자 1 | 2 | 0 | 2 |
| 작업자 2 | 1 | 0 | 5 |
| 작업자 3 | 0 | 0 | 0 |
이 상태에서 아직 완전 매칭을 만들 수 없으므로, 최소 행/열을 선택하여 0인 칸을 모두 덮을 수 있도록 행/열을 고른다. 위의 경우 3행과 2열을 선택 시 모든 0을 덮을 수 있다. 그러면 덮이지 않은 칸 중 가장 작은 비용은 2행 1열의 1이고, 선택되지 않은 행에 대해 이 값을 빼주는 작업을 시행한다.
| 작업자 \ 작업 | 작업 1 | 작업 2 | 작업 3 |
|---|---|---|---|
| 작업자 1 | 1 | -1 | 1 |
| 작업자 2 | 0 | -1 | 4 |
| 작업자 3 | 0 | 2 | 0 |
덮이지 않은 행에 값을 빼주는 작업을 통해 음수값이 발생하였다. 음수를 제거하기 위해서 2열에 다시 1을 더하는 작업을 시행한다.
| 작업자 \ 작업 | 작업 1 | 작업 2 | 작업 3 |
|---|---|---|---|
| 작업자 1 | 1 | 0 | 1 |
| 작업자 2 | 0 | 0 | 4 |
| 작업자 3 | 0 | 3 | 0 |
이 단계에서 작업자1 - 작업2, 작업자2 - 작업 1, 작업자3 - 작업3의 완전 매칭이 발생하였고, 이 경우가 가장 적은 비용으로 작업을 완수할 수 있는 경우다.
아래의 코드는 프로젝트에서 사용한 헝가라인 알고리즘의 구현으로, Formation을 이루는 각각의 Agent들의 움직임이 최소화 되도록 Agent들이 이동해야 하는 자리를 배정하는 문제를 푸는데 사용하였다. 파라미터로 주어지는 CostMatrix는 Formation을 구성하는 DataAsset으로 부터 추출한다.
void FFormationHungarian::Solve(const TArray<TArray<float>>& CostMatrix,
TArray<int32>& OutRowToCol,
TArray<int32>& OutColToRow)
{
const int32 Num = CostMatrix.Num();
OutRowToCol.Init(-1, Num);
OutColToRow.Init(-1, Num);
TArray<float> RowLabel; RowLabel.Init(0.0f, Num + 1); // 각 행의 라벨 u[i]
TArray<float> ColLabel; ColLabel.Init(0.0f, Num + 1); // 각 열의 라벨 v[j]
TArray<int32> ColMatch; ColMatch.Init(0, Num + 1); // ColMatch[col] = 이 열에 매칭된 행
TArray<int32> PrevColumn; PrevColumn.Init(0, Num + 1); // 증가 경로 복원용 배열 이 열로 오기 전의 열
// 각 행에 대해, 매칭을 하나씩 늘려가는 작업 수행
for (int32 Row = 1; Row <= Num; ++Row)
{
ColMatch[0] = Row; // 0번 열(더미 열)에 현재 확장하고자 하는 행 Row 를 연결
int32 CurCol = 0; // 현재 탐색 중인 열 인덱스 초기값
// Slack[col]: 현재 라벨 상태에서, col 열에 새 0-간선을 만들기 위해 필요한 최소 여유값
// Visited[col]: 증가 경로 탐색에서 이미 처리한 열인지 표시
TArray<float> Slack; Slack.Init(FLT_MAX, Num + 1);
TArray<bool> Visited; Visited.Init(false, Num + 1);
// 증가 경로를 찾거나 라벨을 조정하면서 유효 0-간선을 만들어낼 때까지 반복
do
{
Visited[CurCol] = true; // 현재 열 방문 표시
int32 CurRow = ColMatch[CurCol]; // 이 열에 매칭된 행 (0이면 더미)
float BestDelta = FLT_MAX; // 이번 단계에서 라벨을 얼마나 조정할지의 최소값
int32 NextCol = 0; // 그에 따라 새로 선택할 열
// 아직 방문하지 않은 모든 열에 대해 Slack 갱신 및 BestDelta, NextCol 결정
for (int32 Col = 1; Col <= Num; ++Col)
{
if (Visited[Col]) continue;
// CostDiff = 실제 비용 - (행 라벨 + 열 라벨)
// 0 이면 유효 0-간선, 양수면 그만큼 더 라벨을 조정하면 0-간선이 될 수 있음
float CostDiff = CostMatrix[CurRow - 1][Col - 1]
- RowLabel[CurRow]
- ColLabel[Col];
// 해당 열에 대해, 지금까지 본 것들 중 가장 작은 CostDiff 를 Slack 에 저장
if (CostDiff < Slack[Col])
{
Slack[Col] = CostDiff;
PrevColumn[Col] = CurCol; // 이 열로 오기 직전의 열(증가 경로 부모) 저장
}
// 가장 작은 Slack 값을 갖는 열을 NextCol 로 선택
if (Slack[Col] < BestDelta)
{
BestDelta = Slack[Col];
NextCol = Col;
}
}
// 라벨과 Slack 을 한 번에 업데이트
for (int32 Col = 0; Col <= Num; ++Col)
{
if (Visited[Col])
{
// 트리 안에 있는 열들에 대해서, 그 열에 매칭된 행의 라벨을 올리고, 열 라벨은 내린다.
RowLabel[ColMatch[Col]] += BestDelta;
ColLabel[Col] -= BestDelta;
}
else
{
// 아직 트리 밖에 있는 열들에 대해서는 Slack 에서 BestDelta 를 빼준다.
// → 어떤 열에서는 Slack 이 0 이 되어 새로운 0-간선이 생긴다.
Slack[Col] -= BestDelta;
}
}
// 다음으로 탐색할 열로 이동
CurCol = NextCol;
// ColMatch[CurCol] == 0 이 되는 순간, 매칭되지 않은 열에 도달함
} while (ColMatch[CurCol] != 0);
// 증가 경로를 따라가며 매칭을 업데이트하는 단계
// CurCol 는 현재 매칭되지 않은 열에서 시작해, 0번 열까지 거꾸로 올라간다.
do
{
int32 PrevCol = PrevColumn[CurCol]; // 이 열로 오기 전 열
ColMatch[CurCol] = ColMatch[PrevCol]; // 이전 열에 매칭돼 있던 행을 현재 열로 옮김
CurCol = PrevCol; // 한 단계 위(이전 열)로 이동
} while (CurCol != 0); // 0번 열에 도달하면 증가 경로 처리 끝
}
// ColMatch 에 쌓인 열 → 행 매칭 정보를 최종 출력 형식(0-based 인덱스의 행→열, 열→행)으로 변환
for (int32 Col = 1; Col <= Num; ++Col)
{
int32 Row = ColMatch[Col];
if (Row > 0)
{
OutRowToCol[Row - 1] = Col - 1;
OutColToRow[Col - 1] = Row - 1;
}
}
}