본문 바로가기

조합론적 최적화

 (22)
서큘레이션 (Circulation) 최대 흐름 문제(maximum flow problem)는 어떤 방향 그래프(directed graph)와 간선 위의 용량(capacity)으로 정의되는 흐름 네트워크(flow network)에서 시점(source)부터 종점(sink)까지 최대한 많은 양의 물을 흘리는 방법을 찾는 문제입니다. 이 문제는 이론적으로는 물론 산업적으로도 깊이 연구된 매우 중요한 조합론적 최적화 문제입니다. 제 블로그에서도 현재까지 다섯 개의 글을 적었을 만큼 매우 비중 있게 다룬 주제입니다. 이번 포스트에서는 이 문제를 보다 확장을 시켜 보고자 합니다. 원래 문제에서는 각 간선에 이 이상은 흘릴 수 없다는 제약을 주는 용량만 있었습니다. 하지만 경우에 따라서는 각 간선마다 적어도 이 정도는 흐르고 있어야 한다는 일종의 필요량..
A* 알고리즘 (A* Search Algorithm) A* 알고리즘(A* search algorithm), 그동안 개념만 얼추 알고 있던 알고리즘이었습니다. A* 알고리즘은 인공지능 분야에 더 가깝기 때문입니다. 따라서 저도 학부 인공지능 수업 시간에 잠깐 들었던 게 다였죠. 그런데 이번 학기 조교 일을 하면서 어쩌다 보니 A* 알고리즘을 좀 심도 있게 공부해야 할 모종의 사건(?)이 생겼습니다. 처음에는 뭐 이런 것까지 공부해야 하나 싶었지만, 이것저것 찾아 보고 공부하다 보니 웬걸 이론적으로도 흥미로운 내용이 많이 있더군요. 이번 기회에 공부한 내용을 정리하는 겸하여 이 글을 적습니다. 다만 본문의 내용은 제가 이해한 내용을 바탕으로 제 방식대로 재해석하여 적은 것입니다. 따라서 원래 인공지능 분야에서 이해되는 방식과는 다를 수 있습니다. 이점 양지하시..
안정 매칭 (Stable Matching) 오랜만에 글을 적습니다. 미국에서 인턴을 마치고 돌아온 후 그동안 좀 바빴습니다. 인턴을 하는 동안 연구한 결과를 잘 마무리하여 학회에 제출하기도 했고, 이론 컴퓨터 과학을 연구하거나 그것에 관심이 있는 학생들을 모아 교내 학생 모임을 발족하기도 하였습니다. 모쪼록 좋은 결과가 있기를 바라 봅니다. 그러는 와중에 최근 흥미로운 논문을 하나 읽었습니다. 지난 포스트에서 다루었던 다중 슬롯머신 문제(multi-armed bandits)에다가 안정 매칭(stable matching)을 결합한 문제였습니다. 다중 슬롯 머신이 무엇인지 궁금하시면 아래 포스트를 참고하시기 바랍니다. 다중 슬롯머신 문제 & 비적응 탐사 알고리즘 (Multi-Armed Bandits & Non-Adaptive Exploration A..
절단 성질을 이용한 MST 알고리즘 증명 (Proving MST Algorithms by Cut Property) 이 포스트에서 다룰 최소 신장 트리(minimum spanning tree, MST) 문제는 매우 유명한 조합론적 최적화 문제입니다. 아마 이 글을 읽으러 들어오셨다면 아무래도 학부 자료 구조나 알고리즘 수업 시간에 이 문제가 어떤 문제인지에 대해서 들어 보셨을 것입니다. 굳이 다시 정의를 해 보자면, 이 문제는 간선마다 비용이 정의된 그래프 위에서 최소의 비용으로 모든 정점을 연결하는 트리를 찾는 문제입니다. 수업 시간에 이 문제를 다루면서 분명 이 문제를 해결하는 알고리즘에 대해서도 함께 배우셨을 것입니다. 적어도 다음 두 알고리즘은 배웠을 텐데, 바로 크루스칼의 알고리즘(Kruskal's algorithm)과 프림의 알고리즘(Prim's algorithm)입니다. 두 알고리즘 모두 한두 문장으로 설..
경제학으로 해석한 헝가리안 알고리즘 할당 문제(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..
다익스트라의 알고리즘 (Dijkstra's Algorithm) 최단 경로 문제(shortest path problem)는 가장 유명한 조합론적 최적화 문제 중 하나로, 이름에서 유추할 수 있듯이 다양한 분야에서 널리 활용되는 문제입니다. 지난 포스트에서는 이 문제를 정확히 정의하고 최단 경로가 갖는 구조적인 특징을 이해하였으며, 마지막으로 \( O(|V||E|) \) 시간에 이를 해결하는 벨만-포드 알고리즘(Bellman-Ford algorithm)에 대해서도 공부했습니다. 2021.08.22 - [조합론적 최적화/Shortest path] - 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman..
최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) 자동차를 타고 서울에서 부산까지 여행을 떠난다고 생각해 봅시다. 일분일초라도 여행을 더 즐기기 위해서는 빨리 목적지에 도달하는 것이 좋겠죠. 그러려면 어떤 경로를 따라 자동차를 운전해야 할까요? 한 가지 방법으로는 서울에서 부산까지 가는 모든 경로를 따져 본 다음, 가장 빨리 도달할 수 있는 경로를 선택하는 것입니다. 하지만 이 방법은 한눈에 봐도 멍청하다는 것을 알 수 있습니다. 서울에서 부산까지 가는 경로는 엄청나게 많기 때문입니다. 여기서 곰곰이 생각해 보면, 우리는 모든 경로를 다 탐색할 필요가 없어 보입니다. 예를 들어, 서울에서 부산까지 가는데 굳이 둘러 둘러 광주를 경유할 필요는 없겠죠. 반대로 서울과 부산의 가운데 정도에 위치한 대전은 지나는 것이 좋을 것입니다. 과연 어떻게 하면 효율적으..
디니츠의 알고리즘 (Dinitz' Algorithm) 지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다. 가장 최근에는 최대 흐름 문제를 다항 시간에 해결하는 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)을 소개해 드렸죠. 이번에는 에드몬즈-카프 알고리즘보다 더 빠른 시간에 최대 흐름 문제를 해결하는 방법 중 하나를 소개하고자 합니다. 바로 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려진, 디니츠의 알고리즘(Dinitz' algorithm)입니다. 포탈에 검색해 봤더니 디니츠의 알고리즘을 어떻게 구현하는지 우리말로 설명한 게시글은 적잖이 볼 수 있었습니다. 다만 어째서 디니츠의 알고리즘이 에드몬즈-카프 알고리즘보다 효율적으로 동작하는지..
에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때 시점(source)에서 종점(sink)까지 최대로 많은 양의 흐름을 찾는 문제입니다. 이때 흐름은 각 간선에서 용량(capacity)을 넘을 수 없고, 시점과 종점을 제외한 나머지 정점에서는 들어오는 양과 나가는 양이 동일해야 하죠. 지난 포스트에서는 이 문제를 풀기 위하여 잔여 네트워크(residual network)와 증가 경로(augmenting path)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾..

티스토리툴바