반응형
분기한정_상태공간트리
-
알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?알고리즘 2020. 11. 16. 10:22
이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다. 하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안 회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다. 하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다. 그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에 대한 최적 여행 경로를 구할 수 있는지 알아본다. 다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) < TSP(The Travling Salespers..