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

[엄상일 교수의 따끈따끈한 수학] 세계여행 가장 싸게 하는 이동 경로는? 외판원 문제

  ‘도시 n개를 단 한 번만 방문하고 출발점으로 돌아 오려고 한다. 한 도시에서 다른 도시 사이의 거리가 모두 정해져 있을 때 최소 비용이 드는 이동 경로는 무엇일까?’ 문제만 봐서는 안 어려워 보이지만 ‘최소 비용’이라는 말 때문에 외판원 문제를 해결하기가 매우 어렵습니다. 아주 좋은...(계속)
글 : 엄상일(KAIST 수리과학과 교수) 진행 조가현 기자(gahyun@donga.com)
기타 : [일러스트] 오승만
참고자료 : 올라 스벤손, 야쿠프 타르나프스키, 라슬로 베그흐, ‘A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem’, 리차드 립튼, 케네스 레이건 ‘rjlipton.wordpress.com: A TSP Breakthrough’, 에리카 클라레이치 ‘Quantamagazine: Computer Scientists Take Road Less Traveled’
이미지 출처 : ⓒ워털루대학교

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