주메뉴바로가기 본문바로가기

part 4. 무한히 많은 도시 여행하기

여기서 문득 방문하고 싶은 도시가 10만 개라면 어떻게 해야 할 지 궁금해졌습니다. 지금까지 최고 기록은 8만 5900개 도시를 방문하는 거였으니까요. n개의 도시를 여행하는 외판원 문제는 ‘NP-완전’이에요. 어쩌면 n의 다항식 꼴로 표현되는 특정 횟수(다항 시간) 안에 풀 수 있는 방법이 없을 수도 있지요...(계속)
글 : 조혜인 수학동아 heynism@donga.com
도움 : 이희상(성균관대학교 기술경영전문대학원장)
도움 : 이상호(이화여자대학교 컴퓨터공학과 교수)

수학동아 2018년 12호
이전
다음
1
위의 콘텐츠는 유료 서비스입니다. 기사 내용 전체를 보시거나 잡지용 PDF를 보시려면 유료 서비스를 이용해주시기 바랍니다. 종이잡지 정기독자는 구독중인 잡지의 모든 콘텐츠를 구독 기간 동안 무료로 이용하실 수 있습니다.
수학동아 2018년 12호 다른추천기사