TSP2 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31. [SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE "이 문제는 가장 짧은 경로를 '효율적으로' 찾는 것이 목적이 아니다." 라는 것을 보아하니 모든 경로를 방문하는 dfs를 구현해서 풀어보라는 문제같다.나는 외판원순회(TSP)로 풀었다. N+2개의 좌표간 최단 거리를 구해서 배열에 저장해둔다.메모이제이션을 위해 (방문한 고객 인덱스들, 현재 좌표 인덱스) 를 인덱스로 하는 배열을 하나 만든다.이 배열에는 현재 좌표 인덱스부터 아직 방문하지 않은 고객들을 모두 방문한 후 집으로 돌아가는 경로 거리 중.. 2019. 1. 8. 이전 1 다음
