[알고리즘] 외판원 순회

[블로그 이전]

2023.08.16

 

Traveling Salesman problem (TSP)

​

1. 순회니까 시작점이 어디든 결과는 같음 ⇨ A~>A 만 계산
2. 겹치는 경로가 많음 ⇨ dp 사용
3. n <= 16 임 ⇨ visited를 비트 연산으로 해도 됨.

​

​

이해하기 어려웠던게 TCP()가 하는 일임. 도대체 뭘 하냐

​

TCP(now, visited) 라고 할 때,

TCP는 현재 위치가 now이고, visited를 방문한 상태에서 다시 A로 돌아가는 경로의 최소 비용을 구함.

​

따라서 TCP(A,A)는 아래 빨간 경로의 최소비용을 구함. (실은 TCP(0,1))

​

DP{now][visited]도 같은 일을 함.

그래서 아래 경우 D~>A로 되돌아가는 경로의 최소비용을 저장하고 있으므로 더 빨리 구할 수 있음.

​

​

도대체 이런 생각은 누가 처음에 어떻게 한 건지 참 대단하다는 생각...

//TCP psuedo

int TCP(int now, int visited)
{
    모든 장소 방문 시 
        return cost[now][0]

    DP[now][visited] 존재 시
        return DP[now][visited]

    둘 다 아니면
    for(int next=0 ~> n)
        now ~> next 경로가 없으면 : continue
        next가 방문 한 곳이면 : continue
        모두 아니면
            dp[next][visited에 next추가] + cost[now][next]
            dp[now][visited] 업데이트
    
    return dp[now][visited]
}
​