d라이브러리

‘울면 안 돼~. 울면 안 돼~! 산타 할아버지는 우는 아이에겐 선물을 안 주신대’

저는 울기도 많이 울었고, 나이도 많아서 선물을 받지 못할 것 같아요. 대신 산타 할아버지의 배달을 도우면 콩고물이 떨어질지도~? 오늘은 산타 마을을 만들고, 최적의 배송 경로를 계산해 보겠습니다!

산타 할아버지는 하루 안에 전 세계의 아이들에게 선물을 나눠줘야 합니다. 정해진 시간 안에 많은 곳을 돌아다녀야 한다면 당연히 가장 빠르게 이동할 수 있는 방법을 찾을 겁니다. 수학자도 이 방법을 고민하는데요, 이 문제가 여전히 연구 중인 ‘외판원 문제’입니다!

집 네 곳을 가장 빠르게 배달하려면?

외판원 문제는 최소 비용으로 모든 집을 단 한 번만 방문하고 시작점으로 돌아오는 이동 경로를 구하는 거예요. 여기서 최소 비용은 실제 비용일 수도 있고, 이동 거리일 수도 있어요. 우리는 이동 거리라고 생각하고 산타가 가장 빠르게 돌아올 수 있는 방법을 구해 볼게요.

제가 만든 산타 마을에는 A, B, C, D 4개의 집이 있고, 집들 사이의 거리는 서로 다릅니다. 집은 점, 집과 집 사이의 거리는 선으로 표시하고 선 위에 거리를 적으면 문제를 쉽게 이해할 수 있는 그래프가 그려집니다. 어떤 순서로 도는 게 가장 빠를지 구하기 위해서 먼저 A, B, C, D를 도는 모든 경우의 수를 구해 볼게요. 답은로 24가지입니다.

만약 A-B-D-C-A 순서로 돈다면 A와 B 사이의 거리인 7, B와 D 사이의 거리인 15, D와 C사이의 12, C와 A 사이의 10을 모두 더합니다. 이 순서로 돌 때 거리는 44지요. 이렇게 모든 경우의 이동 거리를 구하고, 그중 가장 작은 값을 고르면 가장 짧은 거리로 배달을 할 수 있어요.

하나씩 따져보니 ‘A-B-C-D-A’, ‘A-D-C-B-A’, ‘B-A-D-C-B’, ‘B-C-D-A-B’, ‘C-B-A-D-C’, ‘C-D-A-B-C’, ‘D-A-B-C-D’, ‘D-C-B-A-D’ 이렇게 8가지 방법으로 이동할 때 거리가 41로 가장 짧아요.

집이 많을수록 계산이 복잡해지는 외판원 문제

방문해야 할 집이 10곳만 되어도 경우의 수는1=362만 8800가지나 됩니다. 100곳, 1000곳으로 늘어나면 손으로 계산하기 어렵겠지요? 수학자는 계산이 번거로운 외판원 문제를 컴퓨터를 사용해 풀어요.

문제를 해결하기 위한 절차나 방법을 공식화한 형태로 나타낸 것을 ‘알고리듬’이라고 하는데, 계산 단계가 적은 알고리듬을 사용할수록 컴퓨터는 더 빠르게 답을 내놓아요. 예를 들어 식 x+7=13을 계산할 때 자연수를 1부터 넣어보는 알고리듬은 6번 만에 답을 찾아요. 그런데 좌변에 미지수, 우변에 상수를 두고 상수를 계산하는 알고리듬은 단번에 계산을 완료하지요.

앞의 문제처럼 모든 경우의 수를 다 따져보는 알고리듬을 ‘완전 탐색 알고리듬’이라고 해요. 이 알고리듬은 정확한 답을 구해주는 대신 숫자가 커지면 계산하는 시간도 늘어나 비효율적이에요. 그래서 수학자들은 외판원 문제를 해결할 효율적인 알고리듬을 찾기 위해 연구하고 있어요!

그동안 매스크래프트를 사랑해 주신 모든 분들 정말 감사드려요. 퓨처 킴은 내년에 더 재미있는 게임 수학 기사로 돌아올게요!