[Algorithm] TSP 세일즈맨 알고리즘
TSP 알고리즘: Traveling Sales Person Problem 은 1 부터 n 까지 도시를 방문하고 다시 처음으로 돌아오는 경로중 가장 작은 비용을 선택하는 문제 1. 완전 탐색 = O(N!) -> n 이 조금만 커도 안됨 2. DP 이미 방문한 노드들의 경로는 다음 경로를 결정할때 영향을 주지 않는다. 다만 이전에 방문 했는지 여부는 영향을 끼친다. 그 이후 값중 최소가 되는 경로를 TSP ( here , visit )로 나타내자. (1 ) visit 를 어떻게 표현할것인가 -> 비트마스크 (방문했으면 1, 아니면 0) // 방문여부만 중요 ex ) 2, 3, 7번 방문 = 1000110 (2) 점화식? here 이후의 선택은 방문하지 않은 i 노드로 가는 경로를 w[ here ] [ i ]..
