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

  • 확대
  • 축소

  ‘도시 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를 보시려면 유료 서비스를 이용해주시기 바랍니다. 정기구독 인증은 PC에서 하실 수 있습니다.

위로