[과학]'외판원 순회 난제' 국내 과학자 풀어

영업사원 L씨는 오늘 거래처 6군데를 들러야 된다. 일단 회사를 출발한 L씨는 가장 가까운 거래처부터 방문하기 시작했다. 그런데 L씨가 선택한 길이 시간과 거리에서 가장 효율적인 것이었을까.

이 같은 문제를 수학에서는 ‘외판원 순회 문제’라고 부른다. 말 그대로 여러 도시를 모두 방문하는 가장 짧은 길을 찾는 문제다. 얼른 생각하기에 쉬워 보이지만 수학의 대표적 난제로 손꼽히는 어려운 문제다. 기본적으로 이 문제를 풀려면 가능한 모든 경우를 다 계산한 다음 최소거리를 여행하는 경로를 선택하면 된다. 그러나 25개 도시를 여행하는 모든 경우의 수를 계산해 최소거리를 구하려면 1GHz의 계산속도를 가진 컴퓨터로도 약 10조년 이상이 걸린다.

이 때문에 전세계에서 많은 과학자들이 외판원 순회 문제를 빨리 풀 수 있는 알고리듬을 개발하는데 몰두하고 있다. 알고리듬이란 문제의 답을 체계적으로 구하는 수학적 과정이다. 서울대 컴퓨터공학부 문병로교수(사진)는 얼마 전 ‘세계 유전 진화연산 학술대회’에서 외판원 순회 문제를 이제까지 나온 어떤 방법보다 빠르게 풀 수 있는 알고리듬을 개발했다고 발표했다.

외판원 순회 문제의 경우 수학의 일차식이나 이차식처럼 한정된 시간에 쉽게 답이 나오지 않기 때문에 여러 답을 서로 비교해 그 가운데 나은 것을 최고 근사치로 선택한다. 문 교수는 인텔 셀러론 CPU를 장착한 500㎒ PC로 318, 532, 783, 1000, 2392, 3038개의 도시를 경유하는 문제를 100회 풀어본 결과 이제까지 나온 어떤 해보다 짧은 경로를 얻을 수 있었으며, 평균치 역시 가장 짧았다. 처리 속도 면에서도 월등했다.

문 교수가 사용한 방법은 이른바 ‘유전 알고리듬’이다. 세포 분열 과정에서 자손은 부모로부터 한 쌍의 염색체를 물려받게 된다. 그런데 이 과정에서 인접한 염색체끼리 상대의 염색체 일부를 서로 맞바꾸는 교차가 일어난다. 유전 알고리듬은 이러한 유전현상을 모방해 우선 몇 개의 가능한 해답을 구한 다음 이 해답들을 서로 교차시킨다. 이렇게 생성된 해답 가운데 나은 답들을 선택해 다시 교차시키는 과정을 되풀이하면 가장 좋은 해답을 얻을 수 있다.

문 교수는 이러한 유전 알고리듬의 기본 골격을 유지하면서도 교차과정에서 일어날 수 있는 데이터의 유실을 최소화할 수 있도록 수정했다. 문 교수의 방법은 세계전기전자통신학회(IEEE)의 인정을 받아 올해 이 학회의 ‘진화 연산학회지’에 실릴 예정.

외판원 순회 문제는 전기전자물리 관련 학술지와 학술대회가 대부분 포함돼 있는 데이터베이스인 INSPEC 데이타베이스(www.inspec.org)에 지난 5년 간 1700건이 넘는 논문이 발표될 정도로 각광받는 연구주제다.

그러나 이 문제는 현실 세계에서도 아주 유용하다. 예를 들어 컴퓨터의 기판에 구멍을 뚫을 때 어떤 경로로 드릴이 움직여야 가장 효율적인지를 판단하는 데도 적용되며, 수많은 공중전화의 동전을 수거하는 경우나 요즘 각광받고 있는 택배업에서도 당면한 해결과제다. 또 초대규모집적회로(VLSI) 칩 설계에서도 미세 부품들을 최단거리로 연결하는 데 이용된다.

한편 문 교수는 “인터넷 상의 엄청난 정보를 처리해 개별 고객에게 적합한 광고, 상품, 콘텐츠를 제공하는 데 외판원 순회 문제를 해결한 유전 알고리듬을 이용할 예정”이라고 말했다. 이를 위해 올해 상반기에 벤처도 발족시킬 것이라고 덧붙였다.

<이영완동아사이언스기자>puset@donga.com