TSP (외판원 문제) in 알고리즘 해결전략

  • Jaekwan
    Jaekwan

    오늘 TSP1-TSP2를 풀다가 의문점이 있어서 질문합니다.

    알고리즘 해결전략 p.167에 완전탐색에 의한 솔루션이 있는데요, 이것과 TSP1에 있는 것과 동일한 것 같지 않아서 질문드립니다.

    책 솔루션 : 도시의 순방 1-2-3-1 (첫 도시로 되돌아 오는 것으로 마무리)
    TSP1 : 도시의 경로 1-2-3 (첫 도시로 돌아오진 않음)

    혹시 제가 잘못 볼 수도 있어서 책의 솔루션대로 따라서 했는데,
    2004.2215809991
    1413.7122094895
    이것이 답으로 나오는 군요.

    Sample testcases에는
    1260.3657842490
    841.2045646020

    이 답으로 되어 있고, 답안 확인도 시작한 도시로 돌아오지 않는 것을 답으로 채택하고 있습니다. 확인 부탁드립니다..

    TSP1


    10년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.