TSP 알고리즘 설명 및 백준 2098번 문제 풀이 https://chb2005.tistory.com/86 [JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법 외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거 chb2005.tistory.com

외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거해서 시간복잡도를 줄이는 것 ex) 0, 1, 2, 3, 4, 5 도시가 있다고 생각해보자 모든 도시가 이어져 있을때 모든 경로를 가보려면, 최소 비용을 구하기 위해 (6-1)! = 120개의 경로를 비교해야 함 시간복잡도가 n! 식으로 나오면 n이 13정도만 되어도 1초가 넘어감 시간을 줄일 수 있는 방법을 생각해보자 0->1->2->3->...->0 과 0->2->1->3->...->0 의 상황을 생각해보면 0에서 출발해 1,2,3 도시를 거쳤고 현재 3번 도시에 있는 상황 이 두 상황에서는 4, 5번 도시를..