반응형
공간복잡도
-
알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)알고리즘 2020. 10. 8. 22:25
외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 찾는 알고리즘 start node가 있고 n-1 개의 node를 거쳐 1번 node로 돌아간다. brute-force 알고리즘을 이용해서 문제를 해결할 수도 있지만 n이 20만 되어도 걸리는 시간복잡도는 19!usecs(대략 3857년)으로 평생 구하지 못한다. 하지만 동적프로그래밍을 이용한 TSP알고리즘이면 45초만에 해결가능하다. 그렇다면 예제를 TSP알고리즘을 이용하여 풀어보자 다음과 같이 가중치가 있고, 노드 4개로 이루어진 그래프(V)가 있다. 그리고 위 그래프를 인접매..