외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자
우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘
2019. 6. 27. 04:21
최근댓글