중국 우편배달부 문제

최적설계 수치해석 마지막 수정: 2026-08-17 04:49:37

1. 개요[편집]

중국 우편배달부 문제 Chinese Postman Problem
발표	관메이구(管梅谷, Mei-Ko Kwan) 1960 · 영역판 1962
목표	모든 간선을 최소 비용으로 최소 한 번씩 지나 출발점 복귀
TSP와의 차이	TSP는 정점을 돈다 — 아크 라우팅 대 노드 라우팅
무향 그래프	다항시간 — 홀수차 정점의 최소가중 완전매칭 (Edmonds–Johnson 1973)
핵심 도구	블로섬 알고리즘 · 전점쌍 최단경로
방향 그래프	다항시간 — 최소비용흐름
혼합 그래프	NP-난해 (Papadimitriou 1976)
시골 우편배달부	NP-난해 (Lenstra–Rinnooy Kan 1976)

중국 우편배달부 문제(Chinese postman problem, CPP)는 그래프의 모든 간선을 적어도 한 번씩 지나 출발점으로 돌아오는 폐로 중 총 비용이 최소인 것을 찾는 문제다. 우체부가 담당 구역의 모든 길을 빠짐없이 걷고 우체국으로 돌아와야 한다는 상황에서 나온 이름이며, 노선 검사 문제(route inspection problem)라고도 한다. 중국 산둥사범대의 관메이구가 1960년 중국어 논문에서 정식화했고 1962년 영역판이 나오면서 서구에 알려졌다. “중국인 우편배달부”라는 이름은 미국 국립표준국의 앨런 골드먼이 발표자의 국적을 따 붙인 것이다.¹

외판원 문제와 나란히 놓으면 대비가 선명하다. TSP는 정점을 전부 방문하고 CPP는 간선을 전부 지난다. 목적이 한 칸 옮겨 갔을 뿐인데 복잡도가 통째로 뒤집힌다 — TSP는 NP-난해지만 무향 CPP는 다항시간에 정확히 풀린다. 조합 최적화에서 “무엇을 덮어야 하는가”가 난이도를 얼마나 좌우하는지 보여 주는 가장 깔끔한 쌍이며, 이 계열을 아크 라우팅(arc routing)이라 부른다.

2. 오일러가 이미 반쯤 풀어 놓았다[편집]

간선을 전부 지나되 중복 없이 한 번씩만 지나는 폐로가 오일러 회로다. 1736년 오일러가 쾨니히스베르크 다리 문제에서 내놓은 판정 조건은 다음과 같다.

연결 그래프에 오일러 회로가 존재할 필요충분조건은 모든 정점의 차수가 짝수인 것이다.

필요조건은 자명하다. 회로가 어떤 정점에 들어가면 반드시 나와야 하므로 방문할 때마다 차수를 2씩 소비한다. 충분조건은 히어홀처(1873)의 구성적 증명이 주며, 임의의 폐로를 만들고 아직 쓰지 않은 간선이 남은 정점에서 곁가지 폐로를 만들어 끼워 넣는 방식으로 $O(E)$ 에 회로를 뽑아낸다.²

여기서 CPP의 구조가 바로 드러난다.

그래프가 오일러 그래프면 답은 간선 가중치의 총합이고, 오일러 회로 하나를 뽑으면 끝이다. 여기엔 최적화가 없다.
아니면 어떤 간선은 두 번 이상 지나야 한다. 홀수차 정점에 도착해 나가려면 이미 쓴 간선을 되밟는 수밖에 없기 때문이다.

따라서 CPP는 이렇게 재정식화된다. 어떤 간선들을 복제해서 모든 정점의 차수를 짝수로 만들 것인가 — 복제 비용을 최소로. 복제가 끝나면 오일러 회로 찾기는 선형 시간의 마무리 작업일 뿐이다.

3. 홀수차 정점을 짝지어라[편집]

악수 보조정리에 의해 차수의 총합이 간선 수의 2배이므로, 홀수차 정점의 개수는 언제나 짝수다. 이를 $2k$ 개라 하자. 에드먼즈와 존슨(1973)의 알고리즘은 다음 네 단계다.

홀수차 정점 $T = \{v_1, \dots, v_{2k}\}$ 를 찾는다.
$T$ 의 모든 쌍에 대해 최단경로 거리 $d(v_i, v_j)$ 를 계산한다(다익스트라 $2k$ 회 또는 플로이드-워셜 $O(n^3)$ ).
그 거리를 가중치로 하는 완전그래프 $K_{2k}$ 에서 최소가중 완전매칭을 구한다.
매칭된 쌍마다 대응하는 최단경로 위의 간선을 전부 복제한다. 이제 모든 정점의 차수가 짝수이므로 오일러 회로를 뽑는다.

3단계가 바로 블로섬 알고리즘의 가중 버전이 필요한 지점이다. $K_{2k}$ 는 이분 그래프가 아니므로 헝가리안 알고리즘이 통하지 않는다. 에드먼즈가 1965년에 만든 홀수집합 쌍대변수 기반 원-쌍대 매칭 알고리즘이 여기서 실전 투입되며, CPP는 블로섬 알고리즘의 대표 응용으로 늘 함께 인용된다. 전체 복잡도는 $O(n^3)$ 수준이다.

왜 이게 최적인가. 복제한 간선의 다중집합을 $F$ 라 하면, $F$ 를 더했을 때 모든 정점 차수가 짝수가 되어야 하므로 $F$ 안에서 **홀수 차수를 갖는 정점의 집합이 정확히 $T$ **여야 한다. 이런 간선 집합을 $T$ -조인(T-join)이라 부른다. 최소 $T$ -조인의 각 연결 성분은 (최소성 때문에) $T$ 의 두 정점을 잇는 경로들로 분해되고, 각 경로는 그 두 끝점 사이의 최단경로로 바꿔도 비용이 늘지 않는다. 결국 최소 $T$ -조인 = $T$ 위의 최단경로 거리에 대한 최소가중 완전매칭이 되고, 위 알고리즘이 정확히 그것을 계산한다. 가중치가 음이 아니라는 조건만 있으면 된다.

3.1. 손으로 풀어 보는 예[편집]

정점 $A, B, C, D$ 에 간선 $AB = 1$ , $BC = 1$ , $CD = 1$ , $DA = 1$ , $AC = 3$ 을 두자. 차수는 $A$ 가 3, $B$ 가 2, $C$ 가 3, $D$ 가 2이므로 홀수차 정점은 $A$ 와 $C$ 둘뿐이고, 총 간선 비용은 7이다.

$A$ 와 $C$ 를 잇는 경로는 셋이다 — 직통 $AC$ 가 비용 3, $A\!-\!B\!-\!C$ 가 2, $A\!-\!D\!-\!C$ 가 2. 최단은 2이므로 $A\!-\!B\!-\!C$ (또는 $A\!-\!D\!-\!C$ )의 간선 두 개를 복제한다. 이제 $A$ 와 $C$ 의 차수가 4가 되어 전부 짝수이고, 최적값은 $7 + 2 = 9$ 다.

주목할 점은 직통 간선 $AC$ 를 복제하지 않는다는 것이다. 두 홀수 정점을 잇는다고 해서 그 사이의 간선을 되밟는 것이 답이 아니며, 반드시 최단경로 거리를 써야 한다. 홀수 정점이 넷 이상이면 여기에 “누구를 누구와 짝지을 것인가”라는 매칭 결정이 추가된다.

같은 구조가 근사 알고리즘 쪽에서도 나온다. 메트릭 TSP의 크리스토피디스 $3/2$ -근사가 최소 신장 트리에 홀수차 정점의 최소 매칭을 붙여 오일러 회로를 만든 뒤 지름길을 내는 방식인데, 붙이는 부분이 정확히 CPP의 복제 단계다. 한쪽에서는 정확 알고리즘의 핵심이고 다른 쪽에서는 근사의 핵심이라는 점이 재미있다.

4. 방향 그래프판 — 흐름 문제가 된다[편집]

일방통행이 섞이면 이야기가 달라진다. 방향 그래프의 오일러 회로 조건은

\deg^{+}(v) = \deg^{-}(v) \quad \forall v, \qquad \text{그리고 그래프가 강연결}

이다. 정점마다 불균형 $b(v) = \deg^{+}(v) - \deg^{-}(v)$ 를 정의하면, $b(v) > 0$ 인 정점은 나가는 호가 남고 $b(v) < 0$ 인 정점은 들어오는 호가 남는다. 복제해야 할 호의 다중집합은 이 불균형을 정확히 상쇄해야 하며, 이것은 그대로 최소 비용 흐름 문제다.

$b(v) > 0$ 인 정점을 공급지( $b(v)$ 만큼), $b(v) < 0$ 인 정점을 수요지로 두고, 원래 호를 비용이 가중치이고 용량이 무한인 호로 두어 최소비용흐름을 푼다. 호 $a$ 위의 흐름량 $f_a$ 가 곧 “ $a$ 를 추가로 몇 번 더 지날 것인가”이며, 복제 후 오일러 회로를 뽑으면 끝이다. 최소비용흐름은 다항시간이므로 방향 CPP도 다항시간이다. 네트워크 흐름 표준 도구 그대로.

무향은 매칭, 방향은 흐름 — 둘 다 다항시간인 것이 우연은 아니다. 두 문제 모두 완전 단모듈성 또는 매칭 다면체라는 잘 이해된 다면체 구조 위에 서 있다.

5. NP-난해로 넘어가는 지점[편집]

혼합 그래프. 유향 호와 무향 간선이 섞이면 사정이 급변한다. 무향 간선의 방향을 어떻게 정할지와 어떤 것을 복제할지가 얽혀서, 파파디미트리우(1976)는 혼합 CPP가 NP-완전 문제의 난이도를 가짐을 보였다. 평면 그래프로 제한해도 여전히 어렵다. 하필 실제 도로망이 일방통행과 양방향 도로가 섞인 혼합 그래프라, 가장 현실적인 버전이 가장 어렵다는 얄궂은 상황이 된다. 프레더릭슨(1979)의 2-근사와 $5/3$ -근사가 실무 기준선이다.

바람 부는 우편배달부(windy postman). 같은 무향 간선이라도 방향에 따라 비용이 다른 경우다(오르막·내리막, 물살, 제설차의 우측 배출). 관메이구 본인이 1984년에 이 변형도 NP-난해임을 보였다. 다만 그래프가 오일러 그래프면 다항시간에 풀린다.

시골 우편배달부(rural postman). 모든 간선이 아니라 일부 필수 간선 $E_R \subseteq E$ 만 지나면 되고 나머지는 이동 통로로만 쓰는 문제다. 렌스트라와 리누이 칸(1976)이 NP-난해임을 보였는데, 환원이 직관적이다 — 필수 간선들을 서로 떨어뜨려 놓으면 “필수 성분들을 어떤 순서로 방문할까”가 남고 이것이 곧 TSP다. 필수 간선들이 연결되어 있으면 그 순서 문제가 사라져 보통의 CPP로 환원되고 다시 다항시간이 된다. 즉 난이도의 스위치는 필수 부분그래프의 연결성이다.

용량 제약 아크 라우팅(CARP). 차량 한 대의 적재량·근무시간이 제한되어 여러 경로로 쪼개야 하는 실무 버전으로, 당연히 NP-난해다. 차량 경로 문제의 아크 버전에 해당하며 실제 제설·수거 계획은 전부 여기에 속한다.

6. 구현 규모[편집]

무향 CPP를 실제로 돌릴 때 비용을 지배하는 것은 홀수차 정점의 개수 $2k$ 이지 그래프 전체 크기가 아니다. 최단경로는 $T$ 의 각 정점에서 다익스트라를 한 번씩(총 $O(k \cdot (E + V\log V))$ ), 매칭은 $K_{2k}$ 위에서 $O(k^3)$ 이다. 도시 도로망처럼 대부분의 교차로가 4거리(짝수)인 그래프에서는 $k$ 가 정점 수의 몇 퍼센트에 그쳐, 정점 수만 개짜리 구역도 무리 없이 정확해가 나온다.

가중 일반 매칭 구현은 직접 짜지 않는 것이 정신 건강에 좋다. 콜모고로프의 Blossom V, COIN-OR 계열, LEMON 그래프 라이브러리, 파이썬이면 NetworkX의 max_weight_matching이 표준 선택지다. 최소가중 완전매칭은 가중치를 큰 상수에서 빼 최대가중 완전매칭으로 바꿔 푸는 것이 관례다.

7. 응용[편집]

제설과 살포. 모든 차선을 지나야 하고, 제설날의 방향과 염화칼슘 살포 폭 때문에 방향별 비용이 다르다. 바람 부는 혼합 CPP + 용량 제약이라는 최악 조합이라, 실무는 메타휴리스틱과 구역 분할로 간다.
검침·수거·청소. 가스·수도 검침원, 쓰레기 수거차, 노면 청소차 모두 “구역의 모든 길”이 대상이다. 아크 라우팅 상용 소프트웨어의 주 고객층.
도로·철도·배관 검사. 균열 조사 차량, 궤도 검측차, 배관 내부 검사 로봇(피그)의 순회 계획. 여기서는 필수 구간만 지정되는 경우가 많아 시골 우편배달부가 된다.
절단·플로팅 경로. 레이저·플라즈마 절단이나 펜 플로터는 윤곽선 전체를 지나야 하므로 아크 라우팅이다. 공구를 내린 채 지나는 구간이 필수 간선, 들어 올려 이동하는 구간이 통로라 시골 우편배달부 구조에 정확히 맞는다.
네트워크 시험. 통신망이나 회로 배선의 모든 링크를 검증하는 시험 경로 생성도 같은 틀이다.

주의할 것이 하나 있다. PCB 드릴링은 CPP가 아니다. 구멍은 점이고 순서만 정하면 되므로 그건 외판원 문제다. 같은 PCB라도 배선 패턴을 따라가며 검사하는 작업은 선을 전부 지나야 하므로 아크 라우팅이다. 노드 라우팅과 아크 라우팅을 가르는 기준은 “무엇을 반드시 지나야 하는가”이지 대상 물체가 아니다.³

한편 오일러 경로가 등장하는 유명한 사례 중 DNA 서열 조립의 드브루인 그래프는 CPP가 아니다. 그쪽은 최적화 없이 오일러 경로를 하나 찾는 문제이며, 비용 최소화가 개입하지 않는다는 점에서 이 문서의 주제와 갈린다.

8. 관련 문서[편집]

그래서 이 문제는 사람 이름이 아니라 국적이 붙은 희귀한 사례다. 관메이구 본인은 훗날 인터뷰에서 이 작명을 유쾌하게 받아들였다고 전해진다. 참고로 영어 문헌의 저자 표기 Mei-Ko Kwan은 광둥어 발음을 옮긴 것이라, 같은 사람을 Guan Meigu로도 Kwan Mei-Ko로도 만나게 된다. ↩
오일러의 1736년 논문은 회로가 존재하지 않음을 보인 것이고, 존재 조건의 충분성은 엄밀히는 히어홀처(1873)에 가서야 증명됐다. 137년의 시차가 있는 셈인데, 수학사에서 “자명해 보여서 아무도 안 썼다”의 대표 사례로 종종 인용된다. ↩
이 구분을 놓치면 솔버 선택이 통째로 틀어진다. 실제로 아크 라우팅 문제를 TSP 솔버에 넣으려고 간선마다 중점을 찍어 정점으로 바꾸는 시도가 종종 보이는데, 그러면 “그 간선을 지난다”는 제약이 “그 점을 방문한다”로 약해져서 엉뚱한 경로가 최적으로 나온다. ↩