목록외판원순회 (1)
minkylee
[DP] 외판원 순회(TSP)
어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾는다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? 만약 도시가 20개라고 할 때, 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 20!이다. 20!=2,432,902,008,176,640,000 이기 때문에 시간복잡도가 어마무시하다... 정의 주어진 완전 그래프 G=(v, E)가 연결되어 있고, 가중치가 있는 완전한 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을..
CSE/컴퓨터알고리즘
2024. 4. 18. 18:47