할당문제 (4) 썸네일형 리스트형 경제학으로 해석한 헝가리안 알고리즘 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업 그리고 각 노동자를 각 작업에 할당했을 때 발생하는 비용이 모두 주어졌을 때, 각 노동자를 하나의 작업에 중복 없이 모두 최소의 비용으로 할당하는 방법을 찾는 문제이며, 헝가리안 알고리즘(Hungairan algorithm)은 이 문제를 해결하는 가장 유명한 방법입니다. 할당 문제와 헝가리안 알고리즘은 조합론적 최적화(combinatorial optimization) 분야의 근간을 이루는 개념 중 하나일 뿐 아니라 산업 공학(industrial engineering), 운용 과학(operations research) 등 여러 실용적인 분야에서도 널리 활용됩니다. 이렇게 다양한 분야에서 활약하는 할당 문제와 헝가.. 세제곱 시간 헝가리안 알고리즘 (Hungarian Algorithm in Cubic Time) 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업이 주어지고, 각 노동자-작업 쌍마다 노동자를 작업에 할당할 때의 비용이 주어질 때, 최소의 비용으로 각 노동자를 작업에 하나씩 할당하는 방법을 찾는 문제입니다. 제 블로그에는 할당 문제와 이를 해결하는 알고리즘인 헝가리안 알고리즘(Hungarian algorithm)에 대해 정리한 글이 있습니다. 제 블로그에서 가장 인기가 있는 글이죠. 2019.08.07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm.. 헝가리안 알고리즘 시간 복잡도 분석 지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요. 2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아.. gazelle-and-cs.tistory.com 저기서는 할당 문제가 무엇인지 알아보고.. 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아보니 Hungarian algorithm 자체가 어떻게 동작하는지에 대해서는 우리말로 된 포스팅이 많이 있는 반면에 이 알고리즘이 왜 정확히 돌아가는지에 대해서 분석한 글은 보지 못하였습니다. 제 블로그는 이 간격을 열심히 줄이는 데 초점이 맞추어져 있습니다. 그러니 이번에도 왜 이 알고리즘이 올바른 결과를 출력하는지 함께 알아보도록 하죠. 문제 정의 문제를 정의하기 전에 제 하소연부터 좀 하겠습니다. 이 글을 작성하는 현재 제 자취방 에어컨이 고장 난 상태입니다.. 이전 1 다음
