Problema vânzătorului călător: Python, C++ Algoritm

Ce este problema vânzătorului ambulant (TSP)?

Problema comisarului ambulant (PSA) este o problemă clasică de optimizare combinatorie în informatica teoretică. Având în vedere un graf de orașe, PSA solicită cea mai scurtă cale care vizitează fiecare nod exact o dată și se întoarce la orașul de origine.

Enunțul problemei oferă o listă de orașe împreună cu distanțele dintre fiecare pereche de orașe.

Obiectiv: Începeți din orașul de origine, vizitați fiecare alt oraș exact o dată și întoarceți-vă în orașul de plecare. Scopul este de a găsi cel mai scurt traseu dus-întors posibil.

Exemplu de TSP

Luați în considerare graficul de mai jos, unde 1, 2, 3 și 4 reprezintă orașele, iar ponderea de pe fiecare muchie reprezintă distanța dintre aceste orașe.

Scopul este de a găsi cel mai scurt tur posibil care să pornească din orașul de origine, să viziteze fiecare alt oraș o singură dată și să se întoarcă în orașul de origine.

Pentru graficul de mai sus, ruta optimă este 1-2-4-3-1Costul celui mai scurt tur este 10 + 25 + 30 + 15 = 80.

Diferite soluții la problema vânzătorului călători

Problema comisarului ambulant este clasificată drept NP-dificilă deoarece niciun algoritm cunoscut în timp polinomial nu o rezolvă exact. Complexitatea crește exponențial odată cu numărul de orașe.

Există mai multe modalități de a ataca TSP. Cele mai comune abordări sunt:

Abordarea prin forță brută: Metoda naivă calculează fiecare tur posibil și le compară. Numărul de tururi dintr-un graf cu n orașe este n!, ceea ce face ca forța brută să fie foarte costisitoare din punct de vedere computațional pentru orice spațiu dincolo de zece orașe.

Metoda ramificării și legăturii: Problema este împărțită în subprobleme, iar soluțiile acestor subprobleme se combină într-o soluție optimă. Eliminarea eficientă elimină tururile parțiale care nu pot depăși cel mai bun cost actual.

Acest tutorial demonstrează abordarea programării dinamice, care este versiunea memorizată a funcției branch and bound și se potrivește cu algoritmul Bellman-Held-Karp.

Programare dinamică: Aceasta este o metodă exactă care caută soluția optimă prin reutilizarea suprapuneriiping rezultatele subproblemei. Este mai lent decât cel aproape optim metode lacome, dar returnează întotdeauna un tur optim la nivel global.

Complexitatea computațională a acestei abordări este O(N² × 2^N), despre care vom discuta mai târziu în articol.

Metoda celui mai apropiat vecin: O abordare euristică greedy care sare întotdeauna la cel mai apropiat oraș nevizitat. Este mult mai ieftină decât programarea dinamică, dar nu garantează un tur optim, așa că este utilizată pentru soluții aproape optime atunci când viteza contează mai mult decât minimele exacte.

Algoritm pentru problema vânzătorului ambulant

Folosim abordarea programării dinamice pentru a rezolva TSP. Înainte de a începe algoritmul, să stabilim câțiva termeni:

• Un grafic G = (V, E) este o mulțime de vârfuri și muchii.
• V este mulțimea vârfurilor.
• E este mulțimea muchiilor.
• Vârfurile sunt conectate prin margini.
• Dist(i, j) denotă distanța nenegativă dintre vârfurile i și j.

Presupunem că S este un subset de orașe extrase din {1, 2, 3, …, n} unde i și j sunt două orașe din acel subset. Atunci cost(i, S, j) este lungimea celui mai scurt drum care începe la i, vizitează fiecare oraș din S exact o dată și se termină la j.

De exemplu, cost(1, {2, 3, 4}, 1) reprezintă cea mai scurtă cale unde:

• Orașul de pornire este 1
• Orașele 2, 3 și 4 sunt vizitate o singură dată
• Punctul final este 1

Recurența programării dinamice este:

• set cost(i, {}, i) = 0, ceea ce înseamnă că începem și terminăm la i cu cost zero.
• Atunci când |S| > 1, defini cost(i, S, 1) = ∞ pentru i ≠ 1, deoarece costul real al turului este încă necunoscut.
• Începând cu orașul 1, alegeți următorul oraș astfel încât cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] pentru i ∈ S și i ≠ j.

Pentru graficul de mai sus, matricea de adiacență este următoarea:

Iată cum decurge algoritmul:

Pas 1) Călătoria începe în orașul 1, vizitează fiecare alt oraș o dată și se întoarce în orașul 1.

Pas 2) S este o submulțime a orașelor. Pentru fiecare |S| > 1, se inițializează cost(i, S, 1) = ∞. Aici cost(i, S, j) denotă un tur care începe la i, vizitează orașele din S o dată și ajunge la j. Pornim de la infinit deoarece distanța este necunoscută în acest punct. Deci valorile sunt:

cost(2, {3, 4}, 1) = ∞ înseamnă că începem din orașul 2, trecem prin orașele 3 și 4 și ajungem la 1, cu un cost necunoscut. În mod similar:

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

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

Pas 3) Pentru fiecare submulțime a lui S, calculați:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], În cazul în care j ∈ S și i ≠ j.

Acesta este turul cu cost minim care începe la i, vizitează subsetul de orașe o dată și se întoarce la j. Deoarece turul începe la orașul 1, costul optim este cost(1, {other cities}, 1).

Lucrând la recurență pas cu pas

Acum S = {1, 2, 3, 4}. Există patru elemente, deci numărul de submulțimi este 2^4 = 16Aceste subseturi sunt:

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

Deoarece turul începe din orașul 1, putem elimina fiecare subset care conține orașul 1 în timp ce calculăm costurile intermediare.

Calculul algoritmului se desfășoară după cum urmează:

1) |S| = Φ:

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

2) |S| = 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) |S| = 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) |S| = 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

Deci soluția optimă este 1-2-4-3-1.

Pseudo cod

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)

Implementare in C/C++

Iată implementarea în C++Versiunea de mai jos corectează erorile inițiale ale sursei return eroare, care a revenit după prima permutare în loc să enumere toate tururile.

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

ieșire:

80

Implementarea în Python

Python implementarea reflectă C++ versiune. Corectează sursa from itertools, import virgulă greșeală de scriere, locul greșit return în interiorul buclei interioare și adâncitura rătăcită de pe 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))

ieșire:

80

Soluții academice pentru TSP

Informaticienii au petrecut decenii căutând algoritmi polinomiali îmbunătățiți pentru Problema Comisarului Voiagăn. Până în prezent, TSP rămâne NP-hard.

Mai multe tehnici publicate reduc complexitatea practică pentru anumite familii de instanțe TSP:

• TSP-ul simetric clasic este rezolvat prin Metoda sufixului zero.
• Algoritm de optimizare bazat pe biogeografie utilizează strategii de migrare pentru a rezolva probleme de optimizare care se mapează la TSP.
• Algoritmul evolutiv multi-obiectiv este conceput pentru TSP cu obiective multiple și se bazează pe NSGA-II.
• Sistem multi-agenți Abordarea rezolvă TSP pentru N orașe cu resurse de calcul fixe.
• Euristică Lin-Kernighan și succesorul său LKH oferiți tururi cu o abatere de la 2-3% față de optim pentru cazurile cu milioane de orașe.
• Concordie utilizează planuri de tăiere și ramificare și tăiere pentru a calcula optime exacte pentru instanțe de referință cu zeci de mii de orașe.

Aplicarea problemei vânzătorului călători

Problema comisarului ambulant apare în lumea reală atât în ​​forme pure, cât și modificate. Câteva dintre principalele aplicații sunt:

• Planificare, logistică și fabricarea microcipurilor: Problemele de inserare a cipurilor în industria microcipurilor sunt modelate ca variante TSP pentru a minimiza timpul de deplasare al brațului robotic.
• Secvențierea ADN: Un TSP modificat este utilizat în secvențierea ADN-ului, unde orașele reprezintă fragmente de ADN, iar distanțele reprezintă similaritatea dintre fragmente.
• Astronomie: Astronomii folosesc TSP pentru a minimiza timpul petrecut mutând telescoapele între țintele de observare.
• Control optim: Formulările TSP modelează probleme de control optimal în care trebuie respectate mai multe constrângeri, minimizând în același timp costul traversării.
• Livrare pe ultimul kilometru: AmazonAplicațiile UPS și de livrare de alimente rezolvă variante dinamice de TSP pentru a secvenția opririle șoferilor.
• Colectarea din depozit: Selectorii robotici și umani urmează rute optimizate TSP, care scurtează timpul de călătorie în interiorul centrelor de distribuție.

Analiza complexității TSP

• Complexitatea timpului: Abordarea de programare dinamică Held-Karp rezolvă 2^N subseturi pentru fiecare nod de pornire, dând N × 2^N subprobleme. Fiecare subproblemă necesită un timp liniar pentru a se combina. Dacă nodul de origine nu este specificat, este necesară o buclă externă peste N noduri. Complexitatea totală în timp este O(N² × 2^N).
• Complexitatea spațială: Tabelul DP stochează C(S, i) pentru fiecare submulțime S a mulțimii de vârfuri. Există 2^N subseturi per nod, deci complexitatea spațiului este O(N × 2^N), care este adesea scris ca O(2^N) când N este tratat ca fix.

În continuare, aflați despre Algoritmul Sita lui Eratosthenes.

Întrebări frecvente