외판원순회1 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31. 이전 1 다음
