[https://www.acmicpc.net/problem/2098 ](https://www.acmicpc.net/problem/2098) TSP (Traveling Salesman Problem) NP-hard로 알려진 문제다. 정의는 다음과 같다. > Input: An nxn size matrix Output: A cyclic permutation that minimizes $c(π) = \sum{i=1}^{n}d{i, π(i)}$ where π is a cyclic permutation, π: {1, ... ,n} -> {1, ... ,n}. 즉 n개의 도시를 순회할 때, 비용의 총합이 최소가 되는 경로를 찾는 문제다. Hamiltotion cycle을 TSP의 threshold version problem으로 reduce하여 TSP가 NP-hard임을 증명할 수 있다. TSP의 특수한 케이스인 metric TSP의 경우, 1.5-approximation a