동아사이언스

이미지 확대하기

여기서 문득 방문하고 싶은 도시가 10만 개라면 어떻게 해야 할 지 궁금해졌습니다. 지금까지 최고 기록은 8만 5900개 도시를 방문하는 거였으니까요. n개의 도시를 여행하는 외판원 문제는 ‘NP-완전’이에요. 어쩌면 n의 다항식 꼴로 표현되는 특정 횟수(다항 시간) 안에 풀 수 있는 방법이 없을 수도 있지요...(계속)

글 : 조혜인 기자 heynism@donga.com
도움 : 이희상(성균관대학교 기술경영전문대학원장)
도움 : 이상호(이화여자대학교 컴퓨터공학과 교수)
수학동아 2018년 12호