본문 바로가기

TSP

[알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 6. 15. [알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java) 외판원 순회 문제 (TSP: Travelling Salesman Problem) TSP(Travelling Salesman Problem, 일명 ‘여행하는 외판원 문제’)는 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나다. 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 즉 해밀턴 순환에 저비용 조건만 추가..
[BOJ] 백준 2098번 외판원 순회 (Java)
Dot Algo∙ DS/PS 2021. 6. 15. [BOJ] 백준 2098번 외판원 순회 (Java) #2098 외판원 순회 난이도 : 골드 1 유형 : DP/ 비트마스킹 / TSP 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net ▸ 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 ..

티스토리툴바

티스토리툴바