Dot Algo∙ DS/알고리즘 개념
2021. 6. 15.
[알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java)
외판원 순회 문제 (TSP: Travelling Salesman Problem) TSP(Travelling Salesman Problem, 일명 ‘여행하는 외판원 문제’)는 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나다. 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 즉 해밀턴 순환에 저비용 조건만 추가..
![[알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/YNKd9/btq7h8yuYCE/XIRpcZ9utSgzGwKmNj7zL1/img.png)