알고리즘2011. 2. 20. 17:04

정합의 문제가 있다. (assignment problem)

이는 n 명의 사람한테 중복없이 n개의 일을 부여하는 방식으로 경제학(?)쪽에서 많이 쓰인단다.


그런데 그냥 중복 없이 배정하는 것은 문제가 되지 않지만

배정시의 총 비용의 합이 최대 (혹은 최소)가 되어야 한다는 것이다.


이를 해결하기 위해  문제를 단순화 시키면

각 열 (사람) 에 대해  행 (일) 에 대한 비용을 계산하여 행렬로 만든다.



이를 행별로, 열별로 중복이 되지 않게 하나씩 선택한뒤 총합을 구하여 최대값을 찾으면 되는 것이다.

Brute Force 방식으로 풀면 이렇게 된다.

1열(첫번째 사람)에서 3개중에 하나(일)를 선택한다.
2열(두번째 사람)에서 위에 선택한거 제외한 나머지중(2개) 하나를 선택한다.
3열에서 남은거 하나를 선택한다.

총 경우의 수는 3 x 2 x 1 = 3! = 6 이 되며 하나하나씩 다 계산해본뒤에 총합이 가장 큰 선택을 구한다.


이 방식을 n X n 행렬로 확장하면 총 경우의 수는 n! 로

O(n!) 어마어마한 시간복잡도를 자랑하게 된다.

10명의 사람이 10개의 일을 해야 하는 경우 

분배할 수 있는 경우의 수는 무려 10! = 3628800 이나 되므로 엄청나게 복잡해진다.



이를 O(n^3) 시간내에 해결하는 알고리즘이 헝가리안 알고리즘 (Kuhn & Munkres)이다.

각종 논문을 보면 이를 Linear Programming 방식으로 해결하여 굉장히 복잡하다.

가장 개념적으로 설명이 잘 되어 있는 pt를 소개한다.




Initialize

최초 세팅은 각 점의 간선들중 최대의 값을 선택한다.

그리고 그 값을 기록한다. (Labeling 한다)

이때 중복되지 않게 모두 선택했다면

이것이 최적해이다. (가능성은 매우 낮겠다)


Labeling?

헝가리안 알고리즘은 각 점에 자신이 가질수 있는 일종의 Flow 값을 가지고 있다.

X 를 x점들의 집합이라고 하고 Y 를 y점들의 집합이라고 하면  label x, label y 두개로 구분되며

알고리즘을 진행하면서 각 점에 해당되는 라벨을 변경하면서 간선들을 찾게 된다.



Alternating Tree?

alternating tree 는 간선이 중복되어 선택이 된 것이다. 

분배는 중복되지 않게 해야되므로 이 문제를 해결하는 것이 핵심이다.

수학적인 표기로 이 알고리즘에서는 S 집합 (x 점들중에 tree에 속한 점들)

T 집합 (y점들중에 tree에 속한 점들) 그리고  Nl(u) (u에서 Equality속성을 만족하면서 뻗어나갈수 있는 간선에 해당되는 y점)

으로 표현한다.


alternating tree 문제를 어떻게 해결하나?

이 tree는 여러개의 x점에서 하나의 y점으로 온다(간선)

해결책은 단순하다 현재 간선을 제외하고

그 x 점과 연결될 수 있는 다른 간선들을 검색해서 가장 기회비용이 우수한 간선을 찾아내어 선택한다.



어떤 간선이 기회비용이 우수한가?

델타값 = 라벨x + 라벨y - 간선의 가중치

이것이 다른 간선보다 최소가 되는 간선이다. (0보단 커야한다)

왜 이렇게 되느냐면  각 라벨의 의미를  그 점에서 해결 할수 있는 최대치라고 하면

간선이 비용이 다른 간선보다  최소가 됨이라 함은 거의 최대치 만큼이나 간선의 가중치를

처리할 수 있음을 뜻한다. 즉 손해보는 양? 이라고 생각하면 되겠다.



라벨재조정?

가장 기회비용이 우수한 간선을 찾았지만 처리할수 있을 만큼보다 손해본것은 사실이다.

어차피 그 간선을 선택하였으므로 라벨을 재조정 한다.

중복이 되었던 x 점들에 대하여 label x 들은 전부 델타값만큼 빼고 label y 는 전부 더한다.



간선을 찾았는데 그 간선이 또 alternating tree를 만들수 있나?

당연하다, 또 중복되어 매칭될수도 있으므로 다시 반복한다.

간선이 alternating tree 를 만들지 않는다면  그 간선은 그 시점에서

최대값 매칭을 보장한다. (반드시 전체 매칭 입장에서 최적값을 보장하는 간선은 아니다)

이 alternating tree를 만들지 않는 간선  즉 선택한 간선의 y값이 free하다면 (기존에 매치된 점이 아니라면)

이 간선을 augmenting path  라고 부른다. 



알고리즘은 언제 끝나는가?

augmenting path를  n 번 찾으면 끝난다. 그런데 이 augmenting path는 각 과정에서 선택되었다고 해서

반드시 그 간선이 고정되는것은 아니다. 알고리즘을 수행하면서 계속 변할수 있다.

중요한건  어떤 간선이 선택되었는가가 아니라, 몇번 선택되었는가이다.





위 PDF 파일에 나온 개념 그대로 충실히 구현하면 몇가지 문제가 있다.

Nl(S) 집합을 계산할 때  O(n^2) 시간만큼 소모할 수밖에 없다. 

이것 때문에 최종 O(n^4)으로 변질될 가능성이 있다.

이를 해결하는 방안이 pdf 뒤쪽에 Complexity 에 나온다.

slacky 라는 새로운 변수를 두는 방안이다.





아래는 이들을 모두 적용하여 구현한 코드이다.




10 by 10 짜리 행렬의 임의의 값들을 배정하고 최적해 (최대매칭)를 찾아보았다.

'알고리즘' 카테고리의 다른 글

유클라디안 스코어  (0) 2011.05.09
Fuzzy C-Means ,  (4) 2011.03.27
헝가리안 알고리즘 hungarian algorithm 구현  (2) 2011.02.20
infix -> postfix, LL(0)  (0) 2010.09.22
전화번호 문제 Dynamic Programming  (0) 2010.05.02
infix -> postfix  (0) 2010.04.13
Posted by 멍충한아싸

댓글을 달아 주세요

  1. 일광면

    블로그도 하셧군요!
    잘보고 갑니다~~~

    2011.03.27 02:34 [ ADDR : EDIT/ DEL : REPLY ]