| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2001년 2월 14일 수요일 오후 02시 01분 25초 제 목(Title): Re: TSP > TSP 를 위해서 주어진 그래프가 fully connected 라면 모르겠지만,, > 그렇지 않은 그래프라면 어쩌겠느냐 라는 경우도 잇습니다.. edge가 없는 node간의 거리를 무한대(혹은 적절히 큰 상수)로 주고는 non-metric TSP를 풀면 됩니다. > 최소의 이동으로 모든 도시를 적어도 한번씩 방문하는 path 를 찾아라.. 한번씩이 아니라 "적어도" 한번씩이라면 edge가 있건 없건 상관없이 두 node간의 최단거리를 그냥 거리로 놓고 metric TSP를 풀면 됩니다. a, b, c 세 node가 있고 a-b:10, b-c:10, c-a:100 이렇게 거리를 주면 한번씩만 방문하는 TSP는 a-b-c-a로 120이지마, 최소 한번씩으로 조건이 바뀌면 c-a 거리를 그냥 20으로 설정해서 a-b-c-a로 풀면 40입니다. (c-a는 c-b-a죠. 이건 답을 출력하는 부분을 조금 손보면 됩니다.) -- 박.. |