Traveling Salesman Problem 1
-
알고스팟 Traveling Salesman Problem 1PS 2020. 1. 7. 17:49
https://algospot.com/judge/problem/read/TSP1 algospot.com :: TSP1 Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 algospot.com n의 크기에 따라 풀이법을 달리해야 하는 유명한 문제라고 한다. 이 문제는 n이 8로 매우 작으므로 완전탐색으로..