[Algorithm] Traveling Salesman Problem 1 (Algospot – TSP1)

By | 2018-09-30

출처

  • https://algospot.com/judge/problem/read/TSP1
  • 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

난이도 

  • (하) – 중 – 상 – 최상 – 풀지 못함

문제 

  • Input으로 최대 8개 도시간의 거리가 주어진다. Salesman이 모든 도시를 한 번씩 다 방문하는데 가장 짧은 거리를 계산하는 문제이다.

후기 

  • 문제를 읽고 Priority Queue로 문제를 풀려고 먼저 생각해보았다. 하지만, 도시의 개수가 8개 정도로 제한이 되어 있어서 단순히 모든 가능한 방법을 다 만들어 보는 완전 탐색 방법을 사용하였다. 추가로 가지치기 (Pruning)이라는 기법에 대해서 읽었던 기억이 나서 같이 적용하면 문제를 한번 풀어보았다.
  • 완전 탐색 방법과 가지치기를 사용하여 문제를 정말 쉽게 풀었다. 한번 실수를 했던 부분은 Float로 연산을 수행하니 소수점 7자리에서 오차가 조금씩 발생하여 Double로 연산을 하도록 변경하였다.

코드

  • 완전 탐색 + 가지치기 방법을 사용한 코드
  • Github 주소: https://github.com/mkblog-cokr/algorithmCode
  • 실행 시간: 8ms (제일 빠른 코드 대비 8배(1ms) 느림)

 

Leave a Reply

Your email address will not be published. Required fields are marked *