여행하는 세일즈맨 문제: Python, C++ 암호알고리즘
사라 첸
여행하는 세일즈맨 문제(TSP)란 무엇입니까?
TSP(여행하는 세일즈맨 문제)는 이론 컴퓨터 과학의 고전적인 조합 문제입니다. 문제는 모든 노드를 한 번만 방문하고 원래 도시로 돌아오는 조건으로 그래프에서 최단 경로를 찾는 문제입니다.
문제 설명은 각 도시 간의 거리와 함께 도시 목록을 제공합니다.
목표: 원래 도시에서 시작하려면 다른 도시를 한 번만 방문하고 다시 원래 도시로 돌아오면 됩니다. 우리의 목표는 왕복 경로를 완료하기 위해 가능한 최단 경로를 찾는 것입니다.
TSP의 예
여기에는 1, 2, 3, 4가 도시를 나타내고 모든 가장자리와 관련된 가중치가 해당 도시 사이의 거리를 나타내는 그래프가 나와 있습니다.
출발 도시에서 시작하여 다른 도시나 노드를 한 번만 방문하면서 그래프를 횡단하고 출발 도시로 돌아오는 여행의 가능한 최단 경로를 찾는 것이 목표입니다.
위 그래프에서 최적의 경로는 최소 비용 경로를 따르는 것입니다. 1-2-4-3-1. 그리고 이 최단 경로의 비용은 10+25+30+15 =80입니다.
여행하는 세일즈맨 문제에 대한 다양한 솔루션
순회 세일즈맨 문제(TSP)는 다항 시간 알고리즘이 없기 때문에 NP-hard 문제로 분류됩니다. 도시 수가 증가함에 따라 복잡성이 기하급수적으로 증가합니다.
여행하는 세일즈맨 문제(tsp)를 해결하는 방법에는 여러 가지가 있습니다. 널리 사용되는 솔루션은 다음과 같습니다.
무차별 대입 접근 방식은 순진한 방법입니다. 여행하는 세일즈맨 문제를 해결하기 위해. 이 접근 방식에서는 먼저 가능한 모든 경로를 계산한 다음 이를 비교합니다. n개 도시로 구성된 그래프의 경로 수는 다음과 같습니다. n! 이러한 무차별 접근 방식에서 여행하는 세일즈맨 문제를 해결하는 것은 계산적으로 매우 비용이 많이 듭니다.
분기 및 바인딩 방법: 이 접근 방식에서는 문제가 하위 문제로 분류됩니다. 이러한 개별 하위 문제의 솔루션은 최적의 솔루션을 제공합니다.
이 튜토리얼에서는 이동하는 판매원 문제를 해결하기 위한 분기 및 바인딩 방법의 재귀 버전인 동적 프로그래밍 접근 방식을 보여줍니다.
동적 프로그래밍 가능한 모든 경로를 분석하여 최적의 솔루션을 찾는 방법입니다. 순회외판원의 문제를 상대적으로 높은 비용으로 해결하는 정확한 해결 방법 중 하나입니다. 탐욕스러운 방법 거의 최적의 솔루션을 제공합니다.
이 접근 방식의 계산 복잡도는 다음과 같습니다. O(N^2 * 2^N) 이에 대해서는 이 기사의 뒷부분에서 논의합니다.
가장 가까운 이웃 방법 는 가장 가까운 이웃 노드를 선택하는 휴리스틱 기반 탐욕적 접근 방식입니다. 이 접근 방식은 동적 접근 방식보다 계산 비용이 저렴합니다. 하지만 최적의 솔루션을 보장하지는 않습니다. 이 방법은 최적에 가까운 솔루션에 사용됩니다.
여행하는 세일즈맨 문제에 대한 알고리즘
TSP(Traveling Salesman Problem)를 해결하기 위해 동적 프로그래밍 접근 방식을 사용합니다.
알고리즘을 시작하기 전에 몇 가지 용어에 대해 알아보겠습니다.
- 정점과 모서리의 집합인 그래프 G=(V, E).
- V는 정점의 집합입니다.
- E는 모서리 집합입니다.
- 정점은 가장자리를 통해 연결됩니다.
- Dist(i,j)는 두 정점 i와 j 사이의 음수가 아닌 거리를 나타냅니다.
S가 도시의 하위 집합이고 {1, 2, 3, …, n}에 속한다고 가정합니다. 여기서 1, 2, 3…n은 도시이고 i, j는 해당 하위 집합의 두 도시입니다. 이제 cost(i, S, j)는 S의 노드를 방문하는 최단 경로의 길이로 정의됩니다. 이는 정확히 한 번 시작점과 끝점을 각각 i와 j로 갖습니다.
예를 들어, 비용(1, {2, 3, 4}, 1)은 최단 경로의 길이를 나타냅니다. 여기서:
- 시작 도시는 1
- 도시 2, 3, 4는 한 번만 방문합니다.
- 종료점은 1
동적 프로그래밍 알고리즘은 다음과 같습니다.
- cost(i, , i) = 0으로 설정합니다. 즉, i에서 시작하고 끝나며 비용은 0입니다.
- 언제 |S| > 1, 우리는 cost(i, S, 1) = ∝ 여기서 i !=1 로 정의합니다. 왜냐하면 처음에는 다른 도시를 거쳐 도시 i에서 도시 1까지 도달하는 데 드는 정확한 비용을 알 수 없기 때문입니다.
- 이제 1시부터 시작하여 둘러보기를 완료해야 합니다. 우리는 이런 방식으로 다음 도시를 선택해야 합니다.
비용(i, S, j)=최소 비용(i, S−{i}, j)+dist(i,j) 여기서 i∈S 및 i≠j
주어진 그림에 대한 인접 행렬은 다음과 같습니다.
| 거리(i,j) | 1 | 2 | 3 | 4 |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
알고리즘이 어떻게 작동하는지 살펴보겠습니다.
단계 1) 저희는 1번 도시에서 출발하여 다른 도시를 한 번 방문하고 1번 도시로 돌아오는 여행을 고려하고 있습니다.
단계 2) S는 도시의 부분 집합입니다. 우리 알고리즘에 따르면 모든 |S| > 1에 대해 거리 cost(i, S, 1) = ∝로 설정합니다. 여기서 cost(i, S, j)는 도시 i에서 시작하여 S의 도시를 한 번 방문한 후 이제 도시 j에 있다는 것을 의미합니다. 아직 거리를 모르기 때문에 이 경로 비용을 무한대로 설정합니다. 따라서 값은 다음과 같습니다.
비용 (2, {3, 4}, 1) = ∝ ; 표기법은 우리가 도시 2에서 시작하여 도시 3, 4를 거쳐 1에 도달한다는 것을 나타냅니다. 그리고 경로 비용은 무한대입니다. 비슷하게-
비용(3, {2, 4}, 1) = ∝
비용(4, {2, 3}, 1) = ∝
단계 3) 이제 S의 모든 부분집합에 대해 다음을 찾아야 합니다.
비용(i, S, j)=최소 비용(i, S−{i}, j)+dist(i,j), 여기서 j∈S 및 i≠j
이는 i에서 시작하여 도시의 하위 집합을 한 번 통과하고 도시 j로 돌아오기 위한 최소 비용 경로를 의미합니다. 여행이 도시 1에서 시작된다는 점을 고려하면 최적의 경로 비용은 = cost(1, {다른 도시}, 1)입니다.
이를 달성할 수 있는 방법을 알아보겠습니다.
이제 S = {1, 2, 3, 4}입니다. 네 가지 요소가 있습니다. 따라서 하위 집합의 수는 2^4 또는 16이 됩니다. 해당 하위 집합은 다음과 같습니다.
1) |에| = 널:
{Φ}
2) |에스| = 1:
{{1}, {2}, {3}, {4}}
3) |에스| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |에스| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |에스| = 4:
{{1, 2, 3, 4}}
1부터 시작하므로 도시 1을 포함하는 하위 집합을 버릴 수 있습니다.
알고리즘 계산:
1) |에| = Φ:
비용 (2, Φ, 1) = 거리(2, 1) = 10
비용 (3, Φ, 1) = 거리(3, 1) = 15
비용 (4, Φ, 1) = 거리(4, 1) = 20
2) |에스| = 1:
비용(2, {3}, 1) = 거리(2, 3) + 비용(3, Φ, 1) = 35+15 = 50
비용(2, {4}, 1) = 거리(2, 4) + 비용(4, Φ, 1) = 25+20 = 45
비용(3, {2}, 1) = 거리(3, 2) + 비용(2, Φ, 1) = 35+10 = 45
비용(3, {4}, 1) = 거리(3, 4) + 비용(4, Φ, 1) = 30+20 = 50
비용(4, {2}, 1) = 거리(4, 2) + 비용(2, Φ, 1) = 25+10 = 35
비용(4, {3}, 1) = 거리(4, 3) + 비용(3, Φ, 1) = 30+15 = 45
3) |에스| = 2:
비용(2, {3, 4}, 1) = 최소 [ dist[2,3]+비용(3,{4},1) = 35+50 = 85,
거리[2,4]+비용(4,{3},1) = 25+45 = 70 ] = 70
비용(3, {2, 4}, 1) = 최소 [ dist[3,2]+비용(2,{4},1) = 35+45 = 80,
거리[3,4]+비용(4,{2},1) = 30+35 = 65 ] = 65
비용(4, {2, 3}, 1) = 최소 [ dist[4,2]+비용(2,{3},1) = 25+50 = 75
거리[4,3]+비용(3,{2},1) = 30+45 = 75 ] = 75
4) |에스| = 3:
비용 (1, {2, 3, 4}, 1) = 최소 [ dist[1,2]+비용(2,{3,4},1) = 10+70 = 80
거리[1,3]+비용(3,{2,4},1) = 15+65 = 80
거리[1,4]+비용(4,{2,3},1) = 20+75 = 95 ] = 80
따라서 최적의 솔루션은 다음과 같습니다. 1-2-4-3-1
의사 코드
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, … , n} of size s
Cost (s, S, 1) = Infinity
for all i Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
C/로 구현C++
구현은 다음과 같습니다. C++:
#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
int min_cost = MAX;
while(next_permutation(vertex.begin(), vertex.end()))
{
int current_cost = 0;
int j = s;
for (int i = 0; i < vertex.size(); i++) {
current_cost += graph[j][vertex[i]];
j = vertex[i];
}
current_cost += graph[j][s];
min_cost = min(min_cost, current_cost);
return min_cost;
}
}
int main()
{
int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };
int s = 0;
cout << tsp(graph, s) << endl;
return 0;
}
출력:
80
에서 구현 Python
from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_cost = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
current_cost += graph[k][j]
k = j
current_cost += graph[k][s]
min_cost = min(min_cost, current_cost)
return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))
출력:
80
TSP에 대한 학술 솔루션
컴퓨터 과학자들은 수년간 순회 세일즈맨 문제에 대한 개선된 다항식 시간 알고리즘을 찾아왔습니다. 지금까지 이 문제는 여전히 NP-hard입니다.
최근 몇 년 동안 복잡성을 어느 정도 줄여주는 다음 솔루션이 발표되었습니다.
- 고전적인 대칭 TSP는 Zero Suffix Method로 해결됩니다.
- 생물지리학 기반 최적화 알고리즘은 TSP로 계획할 수 있는 최적화 문제를 해결하기 위한 이주 전략을 기반으로 합니다.
- Multi-Objective Evolutionary Algorithm은 NSGA-II 기반의 다중 TSP를 해결하기 위해 설계되었습니다.
- 다중 에이전트 시스템은 고정된 자원으로 N개 도시의 TSP를 해결합니다.
여행하는 세일즈맨 문제의 응용
여행하는 세일즈맨 문제(TSP)는 가장 순수하고 수정된 형태로 현실 세계에 적용됩니다. 그 중 일부는 다음과 같습니다.
- 마이크로칩 기획, 물류, 제조: 마이크로칩 산업에서는 칩 삽입 문제가 자연스럽게 발생합니다. 이러한 문제는 여행하는 세일즈맨 문제로 계획될 수 있습니다.
- DNA 시퀀싱: 여행하는 외판원 문제를 약간 변형하여 DNA 서열 분석에 사용할 수 있습니다. 여기서 도시는 DNA 조각을 나타내고 거리는 두 DNA 조각 사이의 유사성 척도를 나타냅니다.
- 천문학: 순회 세일즈맨 문제는 천문학자들이 다양한 천체 관측에 소요되는 시간을 최소화하기 위해 적용하는 문제입니다.
- 최적 제어 문제: 여행하는 세일즈맨 문제 공식화는 최적 제어 문제에 적용될 수 있습니다. 몇 가지 다른 제약 조건이 추가될 수 있습니다.
TSP의 복잡성 분석
- 시간 복잡성 : 총 2 개가 있습니다.N 각 노드에 대한 하위 문제. 따라서 하위 문제의 총 개수는 N*2가 됩니다.N. 각 하위 문제를 해결하려면 선형 시간이 필요합니다. 원본 노드가 지정되지 않은 경우 N개 노드에 대해 루프를 실행해야 합니다.
따라서 최적 솔루션에 대한 총 시간 복잡도는 노드 수 * 하위 문제 수 * 각 하위 문제를 해결하는 시간이 됩니다. 시간 복잡도는 O(N2 * 2^N).
- 공간 복잡성 : 동적 프로그래밍 접근 방식은 메모리를 사용하여 C(S, i)를 저장합니다. 여기서 S는 정점 집합의 하위 집합입니다. 총 2개가 있습니다N 각 노드에 대한 하위 집합입니다. 따라서 공간 복잡도는 O(2^N)입니다.
다음으로 알아볼 내용은 에라토스테네스의 체 알고리즘