천천히 꾸준히

헝가리안 알고리즘을 보다 보면 matching과 vertex cover이라는 용어가 계속 나온다.

이게 도대체 무슨 의미길래 계속 나오는가?

vertex cover란?

어떠한 그래프에서의 접점인데, 모든 간선들을 커버하는 접점

도대체 접점은 뭐고, 그래프는 뭐고, 간선은 뭔데???

이러한 기본 지식을 설명하려고 한다.

그래프(graph)

"그래프란 정점(vertex)들이 간선(edge)들로 연결되어 있는 구조"

아래 그림을 보면 이해가 쉽다.

vertex란 선과선이 연결되는 지점, 끝점이며

edge란 정점들을 연결하는 간선이다.

아래에는 6개의 vertex와 5개의 edge가 있는 그래프이다.

자 그러면, 다시 vertex cover의 정의로 돌아가려고 한다.

vertex cover

"어떠한 그래프에서의 접점인데, 모든 간선들을 커버하는 접점"

이제 좀 이해가 가는가? 

아래의 각각의 그래프에서 빨간점은 모두 vertex cover가 된다. 

쉽게 말해 빨간점과 빨간 점에 이어진 선을 모두 제거하게 되면

남아있는 것이 없는 상태가 되는 vertex의 집합을 vertex cover라고 한다.

해당 내용을 기반으로 헝가리안 알고리즘을 다시 한번 보게 되면, 다른 블로그들의 설명을 좀 더 쉽게 이해할 수 있을 것이다. 

https://billionaire-hossa.tistory.com/36

reference

https://namnamseo.tistory.com/entry/Matching%EA%B3%BC-Vertex-cover

https://namnamseo.tistory.com/entry/Tree%EC%9D%98-%EA%B8%B0%EC%B4%88?category=589725

https://brilliant.org/wiki/vertex-cover/

SORT 논문을 학습중에 헝가리안 알고리즘이란 것을 쓴다는데... 도대체 이건 또 뭔지 알아보려고합니다.. 

Hungarian Algorithm이란?

헝가리안 알고리즘이라는 것은 assignment problem을 해결하는 최적의 솔루션(optimal solution) 입니다. 

그럼 먼저 assignment problem이 뭔지?,

그리고 어떻게 헝가리안 알고리즘이 사용하는지? 

알아보겠습니다.

assignment problem이란?

직역하면 할당 문제입니다.
어떻게 하면 가장 효과적으로 할당할 것이냐의 문제인데,
예를 들면, 회사에서 외주를 맡겨야 할 일이 3개가 있다고 한다면(식당, 보안, 환경관리)
해당 일들을 3개의 업체에 맡겨야 하는데 어떻게 맡기는것이 가장 효과적인가 하는 문제입니다.

아래는 각 업체별 업무에 따른 가격이 나와있습니다.

Optimal Solution (Hungarian algorithm)

위와 같은 상황에서 어떻게 하면 회사는 가장 저렴한 가격으로 각각의 업무를 부여할 수 있을까요?

이것을 해결하는 방법은 다음과 같은 절차를 따릅니다.  

1. 행에 대해서 가장 작은 값으로 뺀다

    -> 이 이유는 A업체에 각각에 비용에 3을 빼더라도 환경관리가 가장 싸고, 보안관리가 가장 비싸다는 내용 자체의 변화는 없기 때문입니다. 동일하게 행에 해당하는 B,C 업체도 동일하게 진행해줍니다.   

2. 열에 대해서 가장 작은값으로 뺀다.

이유는 동일합니다. 식당일은 1을 빼더라도 A,C업체가 가장 싸고 B업체가 비싼것에는 차이가 없기 때문입니다.

이렇게 얻은 행렬에서 0의 값을 가지는 업체-업무 쌍만 알게된다면 가장적은 비용으로 모든 업무를 처리해 낼 수 있을것입니다. 단 여기서 값에 해당하는 모든 행과 열은 0 이상의 값이여야 최적화를 할 수 있습니다. 

3. 모두가 0이되는 행과 열을(minimum-size vertex cover) 제외하고 가장 작은 값을 찾아 모든 행에 빼줍니다.

4. 음수가 되는 행렬의 원소를 음이 아닌수로 만들어 줍니다. 

최종적으로 A업체 - 식당, B업체 - 환경관리, C업체 - 보안관리가 최적의 선택이라는 결과가 나옵니다.

이 같은 알고리즘이 바로 헝가리안 알고리즘입니다. 

reference

https://gazelle-and-cs.tistory.com/29