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

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

  ‘도시 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
수학동아 2017년 11호 다른추천기사
이 기사를 읽은 분이 본
다른 인기기사는?
Intro. 가볍게, 튼튼하게, 유연하게 기하학으로 만드는 로봇
[수학뉴스] 오각형 테셀레이션 하는 방법은 오직 15가지!
Part 4. 거대로봇, 기하학으로 일어서다
Part 1. 기이한 술법 3가지
[매스미디어] 신비아파트 고스트볼X의 탄생
  • 동아사이언스 바로가기
  • 과학동아 사이언스보드 바로가기
  • 어린이과학동아 어린이수학동아 바로가기
  • 폴리매스 바로가기
  • DS스토어 바로가기
  • 디라이브러리 바로가기
  • 과학동아천문대 바로가기
  • ㈜동아사이언스 | 등록번호 : 서울 아04396 | 등록일자 : 2017년 3월 2일 | 제호 : 동아사이언스 | 발행인 : 장경애 | 편집인 : 김민수
  • ㈜동아사이언스 디라이브러리 | 대표 : 장경애 | 개인정보관리책임자 : 최수정(privacy@dongascience.com) | 청소년보호책임자 : 신한식
  • 서울시 용산구 청파로 109, 7층 (04370) ｜ 문의 : 02-6749-2000 ｜팩스 : 02-3148-0789 ｜사업자등록번호 : 101-81-62201 (사업자정보확인)
  • 통신판매업신고번호 : 제2013-서울용산-01101호 ｜온라인 결제를 위한 PG사의 구매안전서비스(가입사실 확인)
  • Copyright © Dongascience. All right reserved.

  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911