tsp
-
TSP알고리즘 2020. 8. 14. 17:23
TSP(Travelling Salesman Problem) : 여행하는 외판원 문제 - 개념 : 도시의 개수와 각 도시간 연결되있는 거리들이 주어질 때, 모든 도시를 한 번씩 방문하고 원래 도시로 돌아올 수 있는 최단 거리 경로를 구하는 문제 -풀이 1. 완전탐색 : 각 도시를 잇는 모든 경로를 다 확인해보는 방법. 재귀 혹은 순열을 이용해서 푸는 방법인데 현실적으로 이 방법을 사용하지 않는다. 도시의 수가 N일때 시간복잡도가 O(N!)으로 엄청난 시간을 필요로 하기 때문이다. 2. dp : memoization으로 풀 수 있다. 점화식dp[i][j] = i번째 도시까지 j상태의 도시를 지나쳐 왔을 때의 최소 비용 (j상태는 몇번 몇번 도시를 방문했었는지 즉, 각 도시의 방문 여부 상태) +) dp를 사..