동아사이언스

이미지 확대하기

  ‘도시 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호