여행하는 세일즈맨 문제: Python, C++ 암호알고리즘

여행하는 세일즈맨 문제(TSP)란 무엇입니까?

외판원 문제(TSP)는 이론 컴퓨터 과학에서 고전적인 조합 최적화 문제입니다. 도시들이 나열된 그래프가 주어졌을 때, TSP는 모든 도시를 정확히 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 문제입니다.

문제 설명에는 도시 목록과 각 도시 쌍 사이의 거리가 제공됩니다.

목표: 출발 도시에서 시작하여 다른 모든 도시를 정확히 한 번씩 방문한 후 다시 출발 도시로 돌아옵니다. 목표는 가능한 가장 짧은 왕복 경로를 찾는 것입니다.

TSP의 예

아래 그래프에서 1, 2, 3, 4는 도시를 나타내고, 각 간선의 가중치는 도시들 사이의 거리를 나타냅니다.

목표는 출발 도시에서 시작하여 다른 모든 도시를 정확히 한 번씩 방문하고 다시 출발 도시로 돌아오는 가장 짧은 경로를 찾는 것입니다.

위 그래프에서 최적 경로는 다음과 같습니다. 1-2-4-3-1가장 짧은 코스의 비용은 10 + 25 + 30 + 15 = 입니다. 80.

여행하는 세일즈맨 문제에 대한 다양한 솔루션

외판원 문제는 알려진 다항 시간 알고리즘이 없어 정확하게 풀 수 없기 때문에 NP-난해 문제로 분류됩니다. 이 문제의 복잡도는 도시의 수에 따라 기하급수적으로 증가합니다.

TSP를 공격하는 방법은 여러 가지가 있습니다. 가장 일반적인 접근 방식은 다음과 같습니다.

무차별 대입 방식: 단순한 방법은 가능한 모든 경로를 계산하고 비교합니다. n개의 도시가 있는 그래프에서 가능한 경로의 수는 다음과 같습니다. n!이는 약 10개 도시를 넘어서는 경우 무차별 대입 방식이 계산적으로 매우 비싸진다는 것을 의미합니다.

분기 한정법: 이 문제는 하위 문제로 분해되고, 이러한 하위 문제의 해결책들이 결합되어 최적의 해결책이 도출됩니다. 효과적인 가지치기를 통해 현재 최적 비용을 능가할 수 없는 부분 경로들이 제거됩니다.

이 튜토리얼은 다음을 보여줍니다. 동적 프로그래밍 접근 방식이는 분기 한정법의 메모이제이션 버전이며 벨만-헬드-카프 알고리즘과 일치합니다.

동적 프로그래밍: 이는 중복을 재사용하여 최적의 해를 찾는 정확한 방법입니다.ping 하위 문제 결과입니다. 거의 최적에 가까운 결과보다 속도가 느립니다. 탐욕스러운 방법하지만 항상 전역적으로 최적의 경로를 반환합니다.

이 접근 방식의 계산 복잡도는 다음과 같습니다. O(N² × 2^N)이에 대해서는 기사 후반부에서 자세히 다루겠습니다.

최근접 이웃 찾기 방법: 가장 가까운 미방문 도시로 바로 이동하는 휴리스틱 탐욕 알고리즘입니다. 동적 프로그래밍보다 훨씬 저렴하지만 최적의 경로를 보장하지는 않으므로 정확한 최소값보다 속도가 더 중요한 경우 최적에 가까운 해를 찾는 데 사용됩니다.

여행하는 세일즈맨 문제에 대한 알고리즘

우리는 TSP를 해결하기 위해 동적 프로그래밍 방식을 사용합니다. 알고리즘을 시작하기 전에 몇 가지 용어를 정리해 보겠습니다.

• 그래프 G = (V, E) 정점과 간선의 집합입니다.
• V 정점들의 집합입니다.
• E 는 모서리의 집합입니다.
• 정점은 가장자리를 통해 연결됩니다.
• Dist(i, j) 는 정점 i와 j 사이의 음수가 아닌 거리를 나타냅니다.

S를 {1, 2, 3, …, n}에서 추출한 도시들의 부분집합이라고 가정합니다. 여기서 i와 j는 그 부분집합에 속한 두 도시입니다. 그러면 cost(i, S, j) 는 i에서 시작하여 S에 있는 모든 도시를 정확히 한 번씩 방문하고 j에서 끝나는 최단 경로의 길이입니다.

예를 들어, cost(1, {2, 3, 4}, 1) 는 다음 조건을 만족하는 최단 경로를 나타냅니다.

• 시작 도시는 1
• 도시 2, 3, 4는 한 번만 방문합니다.
• 종료점은 1

동적 프로그래밍의 반복은 다음과 같습니다.

• 세트 cost(i, {}, i) = 0즉, 우리는 비용 없이 i에서 시작하고 끝납니다.
• 인셀덤 공식 판매점인 |S| > 1, 정의하다 cost(i, S, 1) = ∞ 을 통한 i ≠ 1왜냐하면 실제 투어 비용이 아직 알려지지 않았기 때문입니다.
• 첫 번째 도시에서 시작하여 다음 도시를 선택하세요. cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] 을 통한 i ∈ S i ≠ j.

위 그래프의 인접행렬은 다음과 같습니다.

알고리즘의 진행 과정은 다음과 같습니다.

단계 1) 여정은 1번 도시에서 시작하여 다른 모든 도시를 한 번씩 방문한 후 다시 1번 도시로 돌아옵니다.

단계 2) S는 도시들의 부분집합입니다. |S| > 1인 모든 경우에 대해 초기화합니다. cost(i, S, 1) = ∞. 이리 cost(i, S, j) 이는 i에서 시작하여 S에 속한 도시들을 한 번씩 방문하고 j에 도달하는 경로를 나타냅니다. 이 시점에서는 거리가 알려지지 않았기 때문에 무한대에서 시작합니다. 따라서 값은 다음과 같습니다.

cost(2, {3, 4}, 1) = ∞ 즉, 도시 2에서 시작하여 도시 3과 4를 거쳐 도시 1에 도달하는 여정이며, 소요 비용은 알 수 없습니다. 마찬가지로:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

단계 3) S의 각 부분집합에 대해 다음을 계산합니다.

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]어디로 j ∈ S i ≠ j.

이는 도시 i에서 시작하여 도시 집합을 한 번씩 방문하고 도시 j로 돌아오는 최소 비용 경로입니다. 경로가 도시 1에서 시작하므로 최적 비용은 다음과 같습니다. cost(1, {other cities}, 1).

재발 방지 단계별 해결 방법

이제 S = {1, 2, 3, 4}입니다. 원소가 네 개이므로 부분집합의 개수는 다음과 같습니다. 2^4 = 16해당 부분집합은 다음과 같습니다.

1) |에스| = 0: {Φ}

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) |에| = Φ:

• cost(2, Φ, 1) = dist(2, 1) = 10
• cost(3, Φ, 1) = dist(3, 1) = 15
• cost(4, Φ, 1) = dist(4, 1) = 20

2) |에스| = 1:

• cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
• cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
• cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
• cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
• cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
• cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45

3) |에스| = 2:

• cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
• cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
• cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |에스| = 3:

• cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

C/로 구현C++

다음은 구현 코드입니다. C++아래 버전은 소스 코드의 초기 오류를 수정합니다. return 모든 경로를 열거하는 대신 첫 번째 순열 이후에 반환되는 버그가 있었습니다.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

The Python 구현 방식은 다음과 같습니다. C++ 버전입니다. 소스의 내용을 수정합니다. from itertools, import 쉼표 오타, 잘못된 위치 return 내부 고리 안쪽과 그 위에 있는 불규칙한 움푹 들어간 부분 s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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에 대한 학술 솔루션

컴퓨터 과학자들은 수십 년 동안 외판원 문제(TSP)에 대한 개선된 다항 시간 알고리즘을 찾기 위해 노력해 왔습니다. 하지만 현재까지 TSP는 NP-난해 문제로 남아 있습니다.

몇몇 기존에 발표된 기법들은 특정 유형의 TSP 문제에 대한 실제적인 복잡성을 줄여줍니다.

• 고전적인 대칭 TSP는 다음과 같이 해결됩니다. 제로 접미사 방식.
• The 생물지리학 기반 최적화 알고리즘 TSP에 해당하는 최적화 문제를 해결하기 위해 마이그레이션 전략을 사용합니다.
• The 다목적 진화 알고리즘 이 알고리즘은 다목적 TSP 문제를 위해 설계되었으며 NSGA-II를 기반으로 합니다.
• The 다중 에이전트 시스템 이 접근 방식은 고정된 계산 자원을 사용하여 N개 도시에 대한 TSP 문제를 해결합니다.
• The Lin-Kernighan 휴리스틱 그리고 그 후계자 LKH 수백만 개의 도시를 대상으로 최적의 경우 2~3% 이내의 오차 범위 내에서 투어를 제공합니다.
• 콩고 드 이 방법은 절단면과 분기-절단법을 사용하여 수만 개의 도시가 포함된 벤치마크 인스턴스에 대한 정확한 최적값을 계산합니다.

여행하는 세일즈맨 문제의 응용

외판원 문제는 순수한 형태와 변형된 형태 모두로 현실 세계에 나타납니다. 주요 응용 분야는 다음과 같습니다.

• 기획, 물류 및 마이크로칩 제조: 마이크로칩 산업의 칩 삽입 문제는 로봇 팔의 이동 시간을 최소화하기 위해 TSP 변형으로 모델링됩니다.
• DNA 염기서열 분석: 변형된 TSP는 DNA 염기서열 분석에 사용되는데, 여기서 도시는 DNA 조각을 나타내고 거리는 조각들 간의 유사성을 나타냅니다.
• 천문학: 천문학자들은 TSP를 사용하여 관측 대상 사이를 이동하는 데 소요되는 시간을 최소화합니다.
• 최적 제어: TSP 공식은 여러 제약 조건을 준수하면서 이동 비용을 최소화해야 하는 최적 제어 문제를 모델링합니다.
• 라스트 마일 배송: AmazonUPS와 음식 배달 앱은 운전자의 정차 순서를 정하기 위해 동적 TSP 변형 문제를 해결합니다.
• 창고 피킹: 로봇과 사람이 함께 상품을 선별하는 작업은 TSP(운송 시간 계획)에 최적화된 경로를 따라 이루어지며, 이를 통해 물류 센터 내부의 이동 시간을 단축합니다.

TSP의 복잡성 분석

• 시간 복잡성 : Held-Karp 동적 프로그래밍 접근 방식은 2를 해결합니다.^N 각 시작 노드에 대한 부분집합을 제공합니다. N × 2^N 하위 문제들입니다. 각 하위 문제를 결합하는 데는 선형 시간이 걸립니다. 시작 노드가 지정되지 않은 경우 N개의 노드를 순회하는 외부 루프가 필요합니다. 전체 시간 복잡도는 다음과 같습니다. O(N² × 2^N).
• 공간 복잡성 : DP 테이블에는 다음이 저장됩니다. C(S, i) 정점 집합의 각 부분 집합 S에 대해 2개가 있습니다.^N 노드당 부분집합이므로 공간 복잡도는 다음과 같습니다. O(N × 2^N)이는 흔히 다음과 같이 표기됩니다. O(2^N) N을 고정된 값으로 취급할 때.

다음으로, 다음에 대해 알아보세요. 에라토스테네스의 체 알고리즘.

자주 묻는 질문