한붓그리기로 우편 배달
골목길을 한 번씩만 돌아오기
눈 내린 겨울 아침, 제설차가 동네의 모든 도로의 눈을 치우고 차고지로 돌아오려고 합니다.
지도를 펼쳐 놓고 모든 길을 최소한 한 번씩 지나가도록 경로를 짜 보세요. 이미 지나간 길을 어쩔 수 없이 다시 지나야 한다면, 겹치는 거리를 최소로 줄이는 가장 경제적인 방법은 무엇일까요?
이야기
Jakob Emanuel Handmann
Public domain · 위키미디어 공용
우편배달부가 담당 구역의 모든 길을 다니고 우체국으로 돌아와야 합니다. 가장 짧은 길은 어떻게 잡을까요?
쾨니히스베르크의 다리와 닮았지만 다릅니다. 그때는 “한 번씩만 지나 돌 수 있나”를 물었습니다. 여기서는 “두 번 지나도 좋으니 가장 짧게”를 묻습니다.
홀수점이 없으면 문제가 없습니다. 한 번씩만 지나 돌 수 있으니 그것이 가장 짧습니다.
홀수점이 있으면 어떤 길은 두 번 지나야 합니다. 그러면 어느 길을 두 번 지날지 고르는 문제가 됩니다. 홀수점끼리 짝을 지어 그 사이를 잇는 가장 짧은 길을 겹쳐 놓으면 됩니다.
이 문제를 1960년에 중국 수학자 관메이구가 다뤘습니다. 그래서 중국인 우편배달부 문제라 부릅니다.
재미있는 것은, 외판원 문제(모든 점을 지나기)는 아주 어려운데 이 문제(모든 선을 지나기)는 효율적으로 풀린다는 점입니다.
🚩 그런데 지금 그 도시에 가면 한붓그리기가 됩니다. 제2차 세계대전의 폭격으로 다리 둘이 사라졌기 때문입니다. 쾨니히스베르크는 이름도 칼리닌그라드로 바뀌었고 다리는 다섯입니다. 오일러가 「안 된다」고 증명한 그 문제가, 정작 도시가 부서지면서 되는 문제가 된 것입니다.
제설차·쓰레기 수거차·우편 배달의 경로가 이 문제입니다. 「모든 길을 한 번씩 지나기」를 중국인 우편배달부 문제라 합니다.
도로가 홀수 개 만나는 교차로를 짝지어 최소 거리로 잇는 방법이 실제 배차 프로그램에 들어 있습니다.
계단 넷 — 같은 사실을 네 깊이로
동네 지도로 해 본다
우리 동네 지도를 점과 선으로 단순하게 바꿔 그려 보세요. 교차로는 점이고 골목길은 선입니다.
한붓그리기가 한 번에 싹 되면 가장 좋겠지만, 홀수점이 4개나 6개 있으면 길이 끊깁니다. 이미 지난 길을 몇 개 덧그려서 한붓그리기가 되도록 만들어 보세요.
모든 길을 한 번씩 지나 보세요
그것이 오일러 회로 — 쾨니히스베르크 다리와 같은 물음입니다.
홀수점을 짝지어 잇기
모든 교차로의 연결선이 짝수 개(오일러 그래프)라면 모든 길을 정확히 한 번씩만 돌아서 제자리로 올 수 있습니다.
하지만 홀수점이 존재한다면 특정 길들을 중복해서 지나야 합니다. 이 문제를 1962년 중국 수학자 관메이구(Kwan Mei-Ko)가 제기하여 중국인 우편배달 문제(Chinese postman problem)라 부릅니다.
되돌아가는 길이 얼마나
그 이어 준 길만큼 두 번 걷게 됩니다.
중국인 우편배달 문제
중국인 우편배달 문제의 핵심은 홀수점들을 서로 짝지어 잇는 최단 경로들의 합을 최소화하는 것입니다.
홀수점들 사이의 최단 거리를 구한 뒤, 그래프 이론의 최소 가중치 완전 매칭(Minimum weight perfect matching) 알고리즘(에드먼즈의 블라섬 알고리즘)을 적용하면 다항 시간 안에 최적해를 정확히 찾아낼 수 있습니다.
가장 짧게 이어 주기
그런데 다항 시간에 풀립니다 — 에드먼즈의 「꽃 알고리즘」입니다.
최적화
모든 변(길)을 방문하는 우편배달 문제는 P-문제(다항 시간에 해결 가능)이지만, 모든 꼭짓점(집)을 방문하는 외판원 문제(TSP)는 NP-난해 문제입니다.
변을 밟느냐 꼭짓점을 밟느냐의 미세한 차이가 계산 복잡도의 거대한 경계를 가릅니다. 오늘날 쓰레기 수거차 경로, 도로 청소차 배차, 택배 집하 최적화의 핵심 운영과학(OR) 알고리즘으로 쓰입니다.
판매원 문제와 다릅니다
한 글자 차이인데 P 와 NP 만큼 다릅니다.
풀어 보기
우편배달 경로의 최적화. 네 지점 A, B, C, D가 있고 연결된 도로망에서 차수가 A:3, B:3, C:4, D:2 라 하자.
(1) 이 도로망에서 중복 없이 모든 길을 한 번씩만 지나 출발점으로 돌아오는 것이 불가능한 까닭을 홀수점의 개수로 설명하시오.
(2) 두 홀수점 A와 B 사이의 최단 거리가 5km일 때, 모든 도로를 최소 한 번 이상 지나 출발점으로 돌아오기 위해 추가해야 하는 최소 중복 거리를 구하시오.
(3) 홀수점이 4개(A, B, C, D)일 때, 이들을 두 쌍으로 짝짓는 모든 경우의 수를 구하시오.
(3) 은 (AB, CD), (AC, BD), (AD, BC) 3가지를 확인하세요.
답과 풀이 보기
(1) 홀수점이 둘(A, B) 이기 때문입니다.
한 점을 들렀다 나오려면 길을 둘씩 짝지어 써야 합니다. 그러니 출발점으로 돌아오는 길이 있으려면 모든 점의 차수가 짝수여야 합니다.
그런데 A 와 B 는 차수가 3 으로 홀수라 한 길이 짝을 못 찾습니다. 그래서 모든 길을 한 번씩만 지나 제자리로 오는 것은 불가능합니다.
(홀수점이 둘이면 A 에서 떠나 B 에서 끝나는 길은 있습니다 — 다만 돌아오지 못합니다.)
(2) 5 km 입니다.
홀수점을 짝수점으로 바꾸려면 A 와 B 를 잇는 길을 한 번 더 걸어야 합니다. 가장 짧게 잇는 길이 5 km 이므로 덧걸음도 5 km 입니다.
그러면 A 와 B 의 차수가 하나씩 늘어 4 와 4 — 모두 짝수가 되어 회로가 생깁니다.
(3) 3 가지입니다.
⭐ 첫 사람의 짝을 셋 중에서 고르면 나머지 둘은 저절로 정해집니다.
일반적으로 개를 짝짓는 방법은 가지입니다 — 홀수점이 여섯이면 15 가지, 여덟이면 105 가지로 빠르게 늘어납니다.
이것이 중국인 우편배달부 문제입니다 (1962 년 관메이구).
쓰레기차, 제설차, 검침원의 길이 지금도 이 셈으로 짜입니다. 안 걸어도 되는 길을 얼마나 줄이느냐가 곧 기름값입니다.
더 멀리
실제 운영에 바로 쓰이는 수학입니다.
- 제설차와 청소차 — 모든 도로를 지나야 하는 차량의 경로입니다
- 검침과 배달 — 골목을 빠짐없이 도는 순서를 짭니다
- 도로 점검 — 모든 구간을 확인하는 최소 경로입니다
이어지는 장
모든 다리를 한 번씩만 건널 수 없다는 1736년 오일러의 절망은, 지나간 길을 최소한으로 다시 지나며 모든 길을 배달하려는 현대의 물류 알고리즘으로 화려하게 부활했습니다 — 제6장 의 다리 문제가 오늘날 도로망 위에서 어떻게 해결되는지 보세요.
영감을 받은 곳
중국 수학자 콴메이코(Meigu Guan, 管梅谷)가 1962년 학술지 『중국수학(Acta Mathematica Sinica)』에 발표한 논문 「Graphic programming using odd and even points」에서 제안한 중국인 우편배달부 문제(Chinese Postman Problem)에서 왔습니다.