| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2002년 10월 29일 화요일 오후 02시 42분 18초 제 목(Title): Re: 시작점이 주어지는 MST ? 시작점으로 반드시 돌아올 필요가 없는 TSP도 시작점으로 돌아오는 TSP로 간단히 고칠 수 있습니다. dummy node를 만들고, 시작점-dummy 간에는 weight를 0으로 연결하고, 다른 모든 노드와 dummy 간에는 "꽤 큰 값"으로 weight를 주면 됩니다. 그리고 원문에는 TSP가 아닌 것처럼 방문한 도시를 다시 들려도 되는 것도 두 노드간의 거리를 두 노드간의 shortest path로 재정의해주면 끝입니다. -- 박.. |