Algorithem/알고리즘 이론
[TSP] 외판원 순회
문제 정의 - 해밀턴 순환 N개의 연결된 도시가 있고, 도시들을 연결하는 길이 있습니다. 길을 통과하는데는 비용이 듭니다. 길마다 비용은 다를 수 있고, 오는길과 가는길의 비용도 다를 수 있습니다. 모든 도시를 딱 한번씩, 전부 방문하고나서 출발 도시로 되돌아오는 방법 가운데 최소 비용의 길을 알고 싶습니다. (최소 비용 해밀턴 순환) 해밀턴 경로: 모든 점을 딱 한번씩만 지나는 경로 해밀턴 순환: 시작점과 끝점이 같은 해밀턴 경로 NP-Hard Traveling Salesman Problem은 조합 최적화 문제의 일종입니다. 대표적인 NP-Hard 문제로 다항시간에 풀 수 있는 해법이 밝혀지지 않았고 그 가능성도 매우 낮은 문제입니다. 간단해보였지만 생각보다 빡센 문제네요ㄷㄷ 시간복잡도 O(N!) O(..
