sgc109   1년 전

대충 재귀적으로 짜봤는데 시간초과가납니다..

물론 N 이 최대 16까지 가능하니 얼핏봐도 매우큰수가 나와서 시간초과가 날것같긴합니다만( N*(N-1)^(N-1) 번 반복되는것같은데 맞나요? )

JM북에서는 TSP 문제에 대해 저 처럼 재귀 적으로 풀었더라구요

음 일단 제가 책을 처음부터 끝까지 다 읽어본게 아니라

이 단순한 알고리즘이 책의 뒷부분에 나오는 개념을 사용하지 않고 해당 단원에 부합하는 방식으로만 풀려다보니

N의 범위가 적은 경우에 대해서만 다룬것일지는 모르겠지만

제가 궁금한건.. 아예 방식을 바꿔야하나요? 아니면 DP를 사용한다던지해서 중복제거를 할 수가 있나요? 어떤식으로하면좋을지힌트부탁드립니다.

@hongjun7

appa   1년 전

"D(i, status) : status인 상태일 때, 마지막으로 방문한 도시가 i일 때 최소 비용"으로 정의할 수 있습니다.

status란, 예를 들어서 1번 도시, 2번 도시, 3번 도시, ... , n번 도시를 방문했다(1), 안했다(0)를 2진수로 들고 있는 자료입니다.

n=4이고, i = 2, 0111이면 2,3,4번 도시를 방문했는데 마지막에 도착한 곳은 2번 도시란 뜻이지요.

위와 같은 dp 정의를 통해 O(2^N * N^2)에 해결 가능합니다.

아마도 제가 알기로는 종만북 bitmask나 DP 부분에 위의 풀이가 있을 겁니다.

sgc109   1년 전

@hongjun7 정말감사합니다!!

댓글을 작성하려면 로그인해야 합니다.