728x90 tsp1 외판원 순회(TSP) 알고리즘 옥장판 파는 세일즈맨...?🚶🏻♂Traveling Salesman Problem외판원순회는 대표적인 CS 문제 중 하나이다.다항 시간에 풀 수 없는 NP 문제로 유명하다. (NP는 다항시간에 풀 수 없으나 다항시간에 검산이 가능함.)최소 비용을 가지는 원순열 을 찾는 문제이다.결론부터 말하자면,💡외판원 순회는 DP + DFS이다.📌조건외판원은 모든 도시를 최소비용으로 한 번씩만 방문하여 처음 도시로 돌아와야 한다.*이는 해밀턴 경로(Hamilton circuit) 라고 부르며, 한붓그리기와 같다.각각의 도시 간의 경로는 방향성이 있고, 비용이 존재하며 어떤 도시들 간에는 경로가 없을 수도 있다.항상 최적의 경로가 존재한다.📌알 수 있는 사실최적의 경로는 어떤 정점에서 시작하든 사이클을 만들어 .. 2024. 8. 20. 이전 1 다음 728x90
