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

다차원 공간의 외로운 여행

끌개의 흡인력을 이기며 최고봉 찾는다

(그림1) 문제공간과 끌개(그림1) 문제공간과 끌개

순회세일즈맨 문제(TSP, Traveling Salesman Problem)는 컴퓨터과학의 대표적 난제 중 하나다. 세일즈맨이 N개의 도시를 모두 한번씩 방문하고 돌아오는 가장 짧은 경로를 찾는 문제다. 방문해야 할 도시 수가 50개면, 방문하는 모든 경로 수는 49!, 즉 6.08×1062개다. 여기서 각각의 경로는 하나의 솔루션이 된다. 최적...(계속)

글 : 문병로 서울대 컴퓨터공학부 moon@soar.snu.ac.kr

과학동아 2003년 08호

태그

이전
다음
1
과학동아 2003년 08호 다른추천기사