티스토리 뷰
헝가리안 알고리즘
0. 주저리주저리
배정 문제(assignment problem)를 해결할 수 있는 알고리즘.
예를 들어 보면 n명의 사람이 n개의 일을 할 때, 어떤 값의 최대(or 최소) 값을 구하는 데 사용된다. 여기서 보통 어떤 값은 비용이나, 효율 등을 적용할 수 있겠다.
정말 간단하게 문제를 접근해보면, brute force의 형태로 모두 대입해 볼 수 있다.
3명이 있다고 했을 때, 사람(1,2,3)과 일(1,2,3)을 매칭 해보자.
1번 사람이 일을 맡을 수 있는 개수 3개, 2번 사람은 2개, 3번 사람은 남는 거 1개. 따라서 3! 만큼 시간이 들고, 따라서 O(n!)의 시간 복잡도를 갖게 된다. (사용불가.)
헝가리안 알고리즘(Hungarian algorithm & Hungarian method, Kuhn & Munkres 등등 여러 가지 이름으로 불림.)은 이 문제를 O(n^3)만큼으로 줄여준다.
[2]를 참조하면 영문이지만 O(n^4)에 대한 알고리즘도 소개하고 있다.
PS공부를 하다가 헝가리안 알고리즘은 다음에 공부해야지 하고 미뤄뒀다가 논문을 읽는데 나왔다. 그냥 공부할 거 미리 한다 생각하고 Google에 찾아봤지만.. 한글로 잘 정리된 블로그가 몇 없어서 나도 다음에 공부하시는 분들에게 도움이 되고자 이렇게 공부했던 걸 정리했다.
※MCMF나 Flow관련 쪽과 비슷한 것 같다. 여기에 제약이 있다면 비용(cost) 행렬이 정방 행렬(square matrix)이어야 한다는 점.
1. 개요
이론적인 부분을 볼 때는 [1], 코드를 살펴볼 때는 [2]를 위주로 참조했다.
우선, 헝가리안 알고리즘에 필요한 정의(?)라고 해야 할까.. Notation들을 정리해보자.
여러 영어로 적혀있어서 거부감이 들지만 찬찬히 살펴보자.
그래프G=(V,E)는이분 그래프이다.(이분 그래프의 성질들은 다 안다고 가정하겠습니다.) 그리고 간선 E는 두 개의 그룹 간에 모두 연결되어있다.(한쪽 그룹에 n개의 정점이 있다면, 총간선의 개수는 n*n입니다.) w(x,y)는 x, y사이의 weight이다.
Free 정점(vertex)은 Matching 할 때 M에 포함되지 않는다면 free 한 정점이라고 할 수 있다.
Alternating Path는
Fig1의 왼쪽 그림을 보면, 파란색이 간선 E이고, 빨간색이 Matching M이다. 이런 M에서, Alternating path는 경로인데, M과 E-M사이의 다른 길(?) 대안(?)인 길을 나타낸다. Y에서 X로 갈때는 Matching에 사용되지 않은 간선, X에서 Y로 갈때는 Matching에 사용한 간선을 타고 간다.
예를 들면, Y1→X2→Y2→X4→Y4→X5→Y3→X3은 alternating이다. 그리고 시작점과 끝점이 free 하기 때문에 augment (augmenting path) 하다고 할 수 있다. 왜냐하면 이 증가 경로를 통해서 Matching의 size를 증가시킬 수 있기 때문이다.
Fig1에서 저 augmenting path를 뒤집으면 3에서 4로 크기가 증가한다.
Alternating tree는 모든 경로가 alternating path인 어떤 free 한 정점 v을 root로 한 tree를 의미한다.
여기서 오른쪽 그림의 파란선이 Alternating Path이고, Y5의 모든 간선이 Alternating Path이다. 따라서 Alternating tree가 된다.
Feasible labeling & Equality Graphs
여기서 Labeling은 약간 뭐랄까.. 해당 Vertex가 cover 할 수 있는 flow의 크기라고 해야 할까?! 약간 그런 느낌으로 와 닿았다.
PDF에 나와있는 수식을 간단히 정리하면, l(x) 같으면 정점 x를 실수인 Labeling값으로 바꿔주는 함수라고 한다. (구현할 때는 그냥 배열 사용.) 그래서, Feasible labeling은 모든 X, Y에 있는 정점 x, y에 대하여, l(x) + l(y) >= w(x, y)를 만족한다고 한다.
Equality Graphs는 이제 어떤 라벨 값 l에 대해서, G=(V, E_l)로 이루어진 그래프인데, 간선 E_l이 어떤 간선이냐면은, l(x) + l(y) = w(x, y)이다.즉, X의 어떤 점 x, Y의 어떤 점 y의 두 label값을 합친 것과 비용(cost, weight)이 같은 간선만 연결한 그래프라고 할 수 있다.
여기서, 이 feasible labeling과 Equality graph를 통해서 Matching M이 최대 비용 매칭이라는 것을 증명할 수 있다.
e는 간선 집합 E의 어떤 하나의 간선이라고 하고, e = (e_x, e_y)로 나타낸다.
M`을 어떤 G에서의 Perfect Matching이라고 하자. (여기서 E_l을 만족할 필요는 없다.)
모든 정점들은 Matching M에서 한 번만 covered 되기 때문에, 다음과 같이 나타낼 수 있다.
다음과 같이 나타낼 수 있고
시그마 안의 라벨의 합들은 정의에 의해서
다시 이렇게 나타낼 수 있다. 다시 말하면
이렇게 나타낼 수 있고,
는 어떤 Perfect Matching에서의 상한 값(upper bound)이라고 할 수 있다.
이번에는 Equality graph를 적용시켜보자 그러면,
이렇게 나타낼 수 있다. 따라서 최대 비용 매칭이라고 할 수 있다.
Alternating Path/Tree를 왜? 정의하는지 왜? 필요하는지 확! 와 닿지 않을 것 같다. Notation정리는 그렇구나.. 뭐.. label을 사용하면 최댓값을 구할 수 있구나 하고 알고리즘으로 넘어가 보자.
알고리즘의 Step으로
0. Labeling l과 matching M 초기화하기.
1. M이 만약에 perfect 하다면 stop. 그렇지 않으면 X 중에서 아무 free 한 정점 u를 선택하고, S={u}, T=Ø로 설정.
2. S의 이웃이 T와 같다면, label을 업데이트하기.
3. S의 이웃이 T와 같지 않다면 이웃-T에 속하는 아무 y를 잡아서,
A. y가 free 하면 u-y는 augmenting path. M을 증가시켜주고 1단계로.
B. y가 matched 되어 있다면, u를 z로 하고 S에 z를 삽입, T에 y를 삽입하고 2단계로.
여기서 이웃은 Equality graph의 간선만 고려하고 N(S)라면 S내의 모든 x점이 뻗어 나갈 수 있는 y점이라고 할 수 있다. S는(x 정점 중에 tree에 속한 점들) T는 (y정점 중에 tree에 속한 점들이라고 할 수 있다.)
약간 알고리즘의 흐름을 살펴보면 Labeling을 엄격하게 잡아서 적은 간선들만 보고, 점차 점차 labeling을 낮춰가면서 볼 수 있는 간선을 늘리면서 매 단계 최적임을 유지한 채 최대 매칭을 찾아나가는 것 같다. 최대 매칭(매칭의 개수 = 정점 개수)이면 바로 함수를 종료한다. 매단 계 최적의 값을 갖고 가기 때문에 가능하다.
2. Code
여기서는 code를 볼 건데 코드는 [2]를 참고했다.
Step별로 살펴보자.
일단 사용할 변수들이다.
#define N 3 //단순 배열 크기
#define INF 987654321 //단순 INF값.
int cost[N][N];
int n, max_match; //n : 사람or일의 개수 max_match 현재 matching의 크기.
int lx[N], ly[N]; //라벨의 값.
int xy[N], yx[N]; //xy[i]는 x의 i번째 정점과 연결된 정점 y의 번호. yx[i]는 반대.
bool S[N], T[N]; //집합 S, T
int slack[N], slackx[N]; //시간복잡도를 줄이기위한 slack
int pre[N]; //마지막 tree를 쫓아갈 때 사용.
Step0의 초기화 과정이다.
void init_labels()
{
memset(lx, 0, sizeof(lx)); //init label
memset(ly, 0, sizeof(ly)); //init label
for (int x = 0; x < n; ++x)
for (int y = 0; y < n; ++y)
lx[x] = max(lx[x], cost[x][y]); //최댓값으로 설정
return;
}
특별한 점은 x기준으로 연결된 간선 중 cost가 가장 높은 간선을 기준으로 한다는 점이다.
Step 1을 보면,
0. M이 만약에 perfect 하다면 stop. 그렇지 않으면 X 중에서 아무 free 한 정점 u를 선택하고, S={u}, T=Ø로 설정.
라고 되어있는데, 이를 코드로 구현해보면
if (max_match == n) return; //finished.
int x, y, root;
queue <int> q;
memset(S, false, sizeof(S)); //init
memset(T, false, sizeof(T)); //init
memset(pre, -1, sizeof(pre)); //init
for (x = 0; x < n; ++x)
if (xy[x] == -1) //집합 X에서 어떤 free한 정점x 선택
{
q.push(x);
root = x; //x는 alternate tree의 root가 됨.
pre[x] = -2; //root의 이전 노드는 -2로 설정.
S[x] = true; //alternate tree에 속하니 집합 S에 삽입.
break;
}
for (y = 0; y < n; ++y) { //집합 S가 변경되었으니 slack값 변경
slack[y] = lx[root] + ly[y] - cost[root][y]; //slack값 변경
slackx[y] = root; //어떤 x로 계산된 slack인지 저장
}
이렇게 된다.
그리고 이제 alternate path를 찾아볼 것이다.
while (true)
{
while (!q.empty()) { //bfs loop
x = q.front(); q.pop();
for (y = 0; y < n; ++y)
if (cost[x][y] == lx[x] + ly[y] && !T[y]) //find edge E_l
{
if (yx[y] == -1) break; //augment path 발견
T[y] = true;
q.push(yx[y]);
add_to_tree(yx[y], x); //tree연결 }
if (y < n) break; //augment path 발견
}
if (y < n) break; //augment path 발견
여기서 BFS탐색을 하는데 equality graph의 정의에 맞게 if문이 있다. S와 연결된 점 y가 free 하면, (yx[y] == -1) augment path이다. 따라서 그에 맞게 처리해주도록 하고, 그렇지 않은 부분을 이 코드에서 다루고 있는데, y가 free하지 않다면 T에 넣어주고, alternating tree에 연결해준다.
void add_to_tree(int x, int prevx)
{ //(prevx, xy[x]) (xy[x], x)가 연결됨
S[x] = true;
pre[x] = prevx;
for (int y = 0; y < n; ++y) //S에 새로운 정점이 들어왔으므로 slack 업데이트
if (lx[x] + ly[y] - cost[x][y] < slack[y])
{
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
return;
}
위위 코드에서 y가 free하지 않았기 때문에 add_to_tree(yx[y],x)가 실행되었다. 그래서 그 not free 한 y와 연결된 x를 S에 넣어준다. S가 갱신이 되었기 때문에 slack도 갱신하는데, 처음 갱신한 것과 다르게 S에 들어있는 x들 중 최솟값을 취할 수 있도록 if문을 추가했다.
Step 2,3의 부분이 남아있다.
이제 남은 Augment() 함수를 살펴보면
//step2
update_labels(); // N_l(S) = T , augment path가 발견되지 않음. 라벨 값 완화
q = queue<int>(); //clear
//step 3
for (y = 0; y < n; ++y)
if (!T[y] && slack[y] == 0) { //slack[y] == 0 는 새로운 E_l
if (yx[y] == -1) //free y발견
{
x = slackx[y]; //x는 y와 연결될 것.
break;
}
else
{
T[y] = true;
if (!S[yx[y]]) //alternating tree를 확장
{
q.push(yx[y]);
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n) break; //augment path 발견.
}
if (y < n) //augmeht path 발견
{
max_match++;
//x, y가 매칭됨.
//root를 만날 때까지 정보 갱신
for (int cx = x, cy = y, ty; cx != -2; cx = pre[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
augment(); //augment경로를 1개 찾음.
}
return;
}
이렇게 쓸 수 있다.
처음 free 한 x를 root로 지정하고, 그 x에서 갈 수 있는 y점들을 찾은 뒤, 그 y가 free 하면 연결, 아니면 처음 지정한 x를 root로 하는 alternating tree에 연결하는 방식으로 점차 넓혀나간다. 그리고 bfs탐색을 다 끝냈는데 새로운 정점이 안 보인다면 라벨 재조정을 통해 간선을 늘려주는 방식. 위의 증명 덕분에 매 반복에서의 선택은 항상 최적(여기서는 최대)의 값을 선택하면서 진행한다. 따라서 n개를 찾자마자 탈출해도 그 값이 최적이라는 것이 보장된다. 간선들을 주고받는 것을 보면 약간 dfs를 이용한 이분 매칭의 진행 양상과 비슷한 것 같다.
int hungarian()
{
int ret = 0;
max_match = 0;
memset(xy, -1, sizeof(xy));
memset(yx, -1, sizeof(yx));
init_labels(); //step 0;
augment(); //step1-3;
for (int x = 0; x < n; ++x)
ret += cost[x][xy[x]];
return ret;
}
Hungarian 함수는 다음과 같고, main함수에서 우리가 만들어 주어야 할 점은 비용 행렬 cost[x][y], n이다.
code
https://github.com/Kibbomi/Algorithm/blob/master/Hungarian.cpp
Reference