외판원문제
-
알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?알고리즘 2020. 11. 16. 10:22
이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다. 하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안 회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다. 하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다. 그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에 대한 최적 여행 경로를 구할 수 있는지 알아본다. 다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) < TSP(The Travling Salespers..
-
알고리즘: 해밀턴 회로문제(Hamiltonian Circuit Problem)(Backtracking 문제)알고리즘 2020. 11. 12. 19:17
해밀턴 회로문제(HCP)를 알아보기전에 외판원 문제(TSP)에 대해 간단히 알아보자 이전에 외판원 문제(TSP)에 대해 포스팅했었다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) 외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 seungjuitmemo.tistory.com 외판원 문제(TSP)의 경우 가장 빠른 방법으로 20개의 도시를 모두 돌고 돌아오는데 걸리는 시간을 계산하면 약 45초가 소요된다. (brute force를 이용하면 19!으로 3800년이상 걸린다) 이번에는..
-
알고리즘: 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)가 있다. 그리고 위 그래프를 인접매..