Travelling Salesman Problem 외판원 순회 알고리즘은 가중치가 주어진 그래프에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하는 알고리즘입니다. 다시 말해, 간선의 가중치가 주어졌을 때 임의의 시작노드에서 출발하여 모든 노드를 탐색한 뒤 다시 시작노드로 돌아올 때의 가중치 합의 최소값을 구하는 알고리즘 입니다. 이때 마지막 노드에서 시작 노드로 돌아오는 것을 제외하고는 노드를 중복하여 탐색해서는 안됩니다. 가장 먼저 떠올릴 수 있는 방법은 완전탐색이 있습니다. 노드가 n개라면 n개의 순열을 만들어 각 경우의 가중치 합을 비교하여 최소값을 구할 수 있습니다. 하지만 이 방법은 $O(n!)$으로 n이 조금만 커져도 사용할 수 없는 알고리즘이 됩니다. DP, memoization 완전탐색에..
