Problem komiwojażera: Python, C++ Algorytm

Na czym polega problem komiwojażera (TSP)?

Problem komiwojażera (TSP) to klasyczny problem optymalizacji kombinatorycznej w informatyce teoretycznej. Biorąc pod uwagę graf miast, TSP pyta o najkrótszą ścieżkę, która przechodzi przez każdy węzeł dokładnie raz i wraca do miasta początkowego.

W opisie problemu podano listę miast i odległości między każdą parą miast.

Cel: Rozpocznij w mieście początkowym, odwiedź każde inne miasto dokładnie raz i wróć do miasta początkowego. Celem jest znalezienie najkrótszej możliwej trasy w obie strony.

Przykład TSP

Rozważ poniższy wykres, gdzie 1, 2, 3 i 4 reprezentują miasta, a waga na każdej krawędzi przedstawia odległość między tymi miastami.

Celem jest znalezienie najkrótszej możliwej trasy, która zaczyna się w mieście początkowym, odwiedza każde inne miasto dokładnie raz i wraca do miasta początkowego.

W przypadku powyższego wykresu optymalna trasa to 1-2-4-3-1Koszt najkrótszej wycieczki wynosi 10 + 25 + 30 + 15 = 80.

Różne rozwiązania problemu komiwojażera

Problem komiwojażera jest klasyfikowany jako NP-trudny, ponieważ żaden znany algorytm działający w czasie wielomianowym nie rozwiązuje go dokładnie. Złożoność rośnie wykładniczo wraz z liczbą miast.

Istnieje wiele sposobów atakowania TSP. Najpopularniejsze podejścia to:

Podejście siłowe: Metoda naiwna oblicza każdą możliwą trasę i porównuje je. Liczba tras na wykresie z n miastami wynosi n!, co sprawia, że ​​siłowe podejście jest bardzo kosztowne obliczeniowo w przypadku miast większych niż dziesięć.

Metoda rozgałęzienia i ograniczenia: Problem jest dzielony na podproblemy, a rozwiązania tych podproblemów łączą się w rozwiązanie optymalne. Skuteczne przycinanie eliminuje częściowe trasy, które nie mogą przebić aktualnego najlepszego kosztu.

Ten samouczek pokazuje podejście programowania dynamicznego, która jest zapamiętaną wersją algorytmu rozgałęzienia i ograniczenia i odpowiada algorytmowi Bellmana-Helda-Karpa.

Programowanie dynamiczne: Jest to dokładna metoda, która polega na poszukiwaniu optymalnego rozwiązania poprzez ponowne wykorzystanie nakładających się elementówping wyniki podproblemu. Jest wolniejszy niż rozwiązanie bliskie optymalnemu chciwe metody, ale zawsze zwraca globalnie optymalną trasę.

Złożoność obliczeniowa tego podejścia wynosi O(N² × 2^N), o czym porozmawiamy później w artykule.

Metoda najbliższego sąsiada: Heurystyczne, zachłanne podejście, które zawsze przeskakuje do najbliższego, nieodwiedzonego miasta. Jest znacznie tańsze niż programowanie dynamiczne, ale nie gwarantuje optymalnej trasy, dlatego stosuje się je w przypadku rozwiązań niemal optymalnych, gdy szybkość ma większe znaczenie niż dokładne minima.

Algorytm problemu komiwojażera

Do rozwiązania problemu TSP stosujemy podejście programowania dynamicznego. Zanim rozpoczniemy algorytm, ustalmy kilka terminologii:

• Wykres G = (V, E) jest zbiorem wierzchołków i krawędzi.
• V jest zbiorem wierzchołków.
• E jest zbiorem krawędzi.
• Wierzchołki są połączone krawędziami.
• Dist(i, j) oznacza nieujemną odległość między wierzchołkami i oraz j.

Załóżmy, że S jest podzbiorem miast wybranych z {1, 2, 3, …, n}, gdzie i oraz j to dwa miasta w tym podzbiorze. Wówczas cost(i, S, j) jest długością najkrótszej ścieżki, która zaczyna się w i, przechodzi przez każde miasto w S dokładnie raz i kończy się w j.

Na przykład, cost(1, {2, 3, 4}, 1) oznacza najkrótszą ścieżkę, gdzie:

• Miasto początkowe to 1
• Miasta 2, 3 i 4 odwiedza się tylko raz
• Punktem końcowym jest 1

Rekurencja programowania dynamicznego jest następująca:

• Zestaw cost(i, {}, i) = 0, co oznacza, że ​​zaczynamy i kończymy na i przy zerowym koszcie.
• Kiedy |S| > 1, zdefiniować cost(i, S, 1) = ∞ dla i ≠ 1, ponieważ prawdziwy koszt wycieczki nie jest jeszcze znany.
• Zaczynając od miasta 1, wybierz kolejne miasto, aby cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] dla i ∈ S oraz i ≠ j.

W przypadku powyższego grafu macierz sąsiedztwa wygląda następująco:

Oto jak działa algorytm:

Krok 1) Podróż rozpoczyna się w mieście 1, odwiedza jednokrotnie każde inne miasto i wraca do miasta 1.

Krok 2) S to podzbiór miast. Dla każdego |S| > 1 zainicjuj cost(i, S, 1) = ∞. Tutaj cost(i, S, j) Oznacza trasę rozpoczynającą się w punkcie i, odwiedzającą miasta w S raz i docierającą do punktu j. Zaczynamy od nieskończoności, ponieważ odległość w tym punkcie jest nieznana. Wartości są zatem następujące:

cost(2, {3, 4}, 1) = ∞ Oznacza to, że zaczynamy w mieście 2, przechodzimy przez miasta 3 i 4 i docieramy do miasta 1, z nieznanym kosztem. Analogicznie:

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

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

Krok 3) Dla każdego podzbioru S oblicz:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Gdzie j ∈ S oraz i ≠ j.

To jest wycieczka o minimalnym koszcie, która rozpoczyna się w i, odwiedza podzbiór miast raz i wraca do j. Ponieważ wycieczka rozpoczyna się w mieście 1, optymalny koszt wynosi cost(1, {other cities}, 1).

Praca z rekurencją krok po kroku

Teraz S = {1, 2, 3, 4}. Elementy są cztery, więc liczba podzbiorów wynosi 2^4 = 16Te podzbiory to:

1) |S| = 0: {Φ}

2) |S| = 1: {{1}, {2}, {3}, {4}}

3) |S| = 2: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3: {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4: {{1, 2, 3, 4}}

Ponieważ wycieczka rozpoczyna się w mieście 1, możemy pominąć każdy podzbiór zawierający miasto 1 podczas obliczania kosztów pośrednich.

Obliczenia algorytmu przebiegają następująco:

1) |S| = Φ:

• koszt(2, Φ, 1) = dystrybucja(2, 1) = 10
• koszt(3, Φ, 1) = dystrybucja(3, 1) = 15
• koszt(4, Φ, 1) = dystrybucja(4, 1) = 20

2) |S| = 1:

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

3) |S| = 2:

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

4) |S| = 3:

• koszt(1, {2, 3, 4}, 1) = min [ dist(1, 2) + koszt(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + koszt(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + koszt(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Tak więc optymalnym rozwiązaniem jest 1-2-4-3-1.

Pseudo kod

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)

Implementacja w C/C++

Oto implementacja w C++Wersja poniżej naprawia wczesną wersję źródła return błąd, który powrócił po pierwszej permutacji zamiast wymienić wszystkie trasy.

#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;
}

Wyjście:

80

wdrożenie w Python

Python wdrożenie odzwierciedla C++ wersja. Poprawia źródło from itertools, import błąd literowy, przecinek źle umieszczony return wewnątrz pętli wewnętrznej i przypadkowe wcięcie na 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))

Wyjście:

80

Rozwiązania akademickie dla TSP

Informatycy od dziesięcioleci poszukują ulepszonych algorytmów wielomianowych dla problemu komiwojażera. Jak dotąd TSP pozostaje problemem NP-trudnym.

Kilka opublikowanych technik redukuje praktyczną złożoność dla określonych rodzin instancji TSP:

• Klasyczny symetryczny TSP jest rozwiązywany przez Metoda sufiksu zerowego.
• Algorytm optymalizacyjny oparty na biogeografii stosuje strategie migracji w celu rozwiązania problemów optymalizacyjnych mapowanych na TSP.
• Wielokryterialny algorytm ewolucyjny jest przeznaczony do wielokryterialnego TSP i bazuje na NSGA-II.
• System wieloagentowy Podejście to rozwiązuje problem TSP dla N miast ze stałymi zasobami obliczeniowymi.
• Heurystyka Lin-Kernighana i jego następca LKH dostarczać wycieczki w zakresie 2-3% od wartości optymalnej w przypadku milionów miast.
• Zgoda wykorzystuje płaszczyzny cięcia i metodę „rozgałęziaj i tnij”, aby obliczyć dokładne wartości optymalne dla przypadków testowych obejmujących dziesiątki tysięcy miast.

Zastosowanie problemu komiwojażera

Problem komiwojażera pojawia się w świecie rzeczywistym zarówno w czystej, jak i zmodyfikowanej formie. Oto niektóre z jego głównych zastosowań:

• Planowanie, logistyka i produkcja mikroprocesorów: Problemy z wkładaniem układów scalonych w przemyśle mikroprocesorowym są modelowane jako warianty TSP w celu zminimalizowania czasu ruchu ramienia robota.
• Sekwencjonowanie DNA: Zmodyfikowana metoda TSP jest wykorzystywana w sekwencjonowaniu DNA, w którym miasta reprezentują fragmenty DNA, a odległości reprezentują podobieństwo między fragmentami.
• Astronomia: Astronomowie wykorzystują technologię TSP, aby zminimalizować czas potrzebny na obracanie teleskopów między celami obserwacji.
• Optymalna kontrola: Formuły TSP modelują problemy optymalnego sterowania, w których konieczne jest przestrzeganie wielu ograniczeń przy jednoczesnym minimalizowaniu kosztów przechodzenia.
• Dostawa ostatniej mili: Amazon, UPS i aplikacje do dostawy żywności rozwiązują dynamiczne warianty TSP w celu ustalenia kolejności postojów kierowców.
• Kompletacja magazynowa: Roboty i ludzie kompletujący zamówienia poruszają się po trasach zoptymalizowanych pod kątem TSP, co skraca czas przemieszczania się wewnątrz centrów dystrybucji.

Analiza złożoności TSP

• Złożoność czasowa: Podejście programowania dynamicznego Helda-Karpa rozwiązuje 2^N podzbiory dla każdego węzła początkowego, dając N × 2^N Podproblemy. Połączenie każdego podproblemu zajmuje czas liniowy. Jeśli węzeł początkowy jest nieokreślony, wymagana jest zewnętrzna pętla obejmująca N węzłów. Całkowita złożoność czasowa wynosi O(N² × 2^N).
• Złożoność przestrzeni: Tabela DP przechowuje C(S, i) dla każdego podzbioru S zbioru wierzchołków. Istnieją 2^N podzbiorów na węzeł, więc złożoność przestrzenna wynosi O(N × 2^N), które często zapisuje się jako O(2^N) gdy N traktujemy jako stałe.

Następnie dowiedz się więcej o Algorytm sita Eratostenesa.

FAQ