Problema del commesso viaggiatore: Python, C++ Algoritmo

Cos’è il problema del commesso viaggiatore (TSP)?

Il problema del commesso viaggiatore (TSP) è un classico problema di ottimizzazione combinatoria nell'informatica teorica. Dato un grafo di città, il TSP richiede di trovare il percorso più breve che visiti ogni nodo esattamente una volta e ritorni alla città di partenza.

Il problema viene descritto fornendo un elenco di città e le distanze tra ciascuna coppia di città.

Obiettivo: Parti dalla città di origine, visita ogni altra città esattamente una volta e torna alla città di partenza. L'obiettivo è trovare il percorso di andata e ritorno più breve possibile.

Esempio di TSP

Si consideri il grafico sottostante, dove 1, 2, 3 e 4 rappresentano le città e il peso di ciascun arco rappresenta la distanza tra tali città.

L'obiettivo è trovare il tour più breve possibile che parta dalla città di origine, visiti ogni altra città esattamente una volta e ritorni alla città di origine.

Per il grafico sopra, il percorso ottimale è 1-2-4-3-1. Il costo del tour più breve è 10 + 25 + 30 + 15 = 80.

Soluzioni diverse al problema del commesso viaggiatore

Il problema del commesso viaggiatore è classificato come NP-difficile perché nessun algoritmo noto in tempo polinomiale è in grado di risolverlo esattamente. La complessità cresce esponenzialmente con il numero di città.

Esistono diversi modi per attaccare il TSP. Gli approcci più comuni sono:

Approccio basato sulla forza bruta: Il metodo ingenuo calcola ogni possibile percorso e li confronta. Il numero di percorsi in un grafo con n città è n!, il che rende il calcolo con la forza bruta estremamente oneroso per qualsiasi cosa che vada oltre una decina di città.

Metodo Branch and Bound: Il problema viene scomposto in sottoproblemi e le soluzioni di questi sottoproblemi si combinano per formare una soluzione ottimale. Un'efficace potatura scarta i percorsi parziali che non riescono a battere il miglior costo corrente.

Questo tutorial dimostra che approccio di programmazione dinamica, che è la versione con memorizzazione dei risultati dell'algoritmo branch and bound e corrisponde all'algoritmo Bellman-Held-Karp.

Programmazione dinamica: Si tratta di un metodo esatto che cerca la soluzione ottimale riutilizzando la sovrapposizioneping risultati del sottoproblema. È più lento rispetto a quello quasi ottimale metodi avidima restituisce sempre un percorso globalmente ottimale.

La complessità computazionale di questo approccio è O(N² × 2^N), argomento che approfondiremo più avanti nell'articolo.

Metodo del vicino più prossimo: Un approccio euristico greedy che sceglie sempre la città non ancora visitata più vicina. È molto più economico della programmazione dinamica, ma non garantisce un percorso ottimale, quindi viene utilizzato per soluzioni quasi ottimali quando la velocità è più importante del minimo esatto.

Algoritmo per il problema del commesso viaggiatore

Utilizziamo l'approccio della programmazione dinamica per risolvere il problema del commesso viaggiatore (TSP). Prima di iniziare l'algoritmo, chiariamo alcuni termini:

• Un grafico G = (V, E) è un insieme di vertici e spigoli.
• V è l'insieme dei vertici.
• E è l'insieme degli spigoli.
• I vertici sono collegati tramite bordi.
• Dist(i, j) indica la distanza non negativa tra i vertici i e j.

Supponiamo che S sia un sottoinsieme di città tratte da {1, 2, 3, …, n} dove i e j sono due città in quel sottoinsieme. Allora cost(i, S, j) è la lunghezza del percorso più breve che parte da i, visita ogni città di S esattamente una volta e termina in j.

Per esempio, cost(1, {2, 3, 4}, 1) indica il percorso più breve dove:

• La città di partenza è 1
• Le città 2, 3 e 4 vengono visitate una sola volta
• Il punto finale è 1

La ricorrenza della programmazione dinamica è:

• Impostato cost(i, {}, i) = 0, il che significa che partiamo e finiamo in i con costo zero.
• Quando |S| > 1, definire cost(i, S, 1) = ∞ per i ≠ 1, perché il costo effettivo del tour non è ancora noto.
• Partendo dalla città 1, scegli la città successiva in modo che cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] per i ∈ S and i ≠ j.

Per il grafico sopra riportato, la matrice di adiacenza è la seguente:

Ecco come procede l'algoritmo:

Passo 1) Il viaggio inizia nella città 1, visita ogni altra città una volta e ritorna alla città 1.

Passo 2) S è un sottoinsieme di città. Per ogni |S| > 1, inizializza cost(i, S, 1) = ∞. Qui cost(i, S, j) indica un tour che inizia da i, visita le città in S una volta e raggiunge j. Partiamo dall'infinito perché la distanza è sconosciuta in questo punto. Quindi i valori sono:

cost(2, {3, 4}, 1) = ∞ significa che partiamo dalla città 2, attraversiamo le città 3 e 4 e raggiungiamo la 1, con un costo sconosciuto. Allo stesso modo:

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

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

Passo 3) Per ogni sottoinsieme di S, calcola:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]Durante la serata, j ∈ S and i ≠ j.

Questo è il tour di costo minimo che inizia da i, visita il sottoinsieme di città una volta e ritorna a j. Poiché il tour inizia dalla città 1, il costo ottimale è cost(1, {other cities}, 1).

Analisi della ricorrenza passo dopo passo

Ora S = {1, 2, 3, 4}. Ci sono quattro elementi, quindi il numero di sottoinsiemi è 2^4 = 16Questi sottoinsiemi sono:

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

Poiché il tour inizia dalla città 1, possiamo scartare ogni sottoinsieme che contiene la città 1 durante il calcolo dei costi intermedi.

Il calcolo dell'algoritmo si svolge come segue:

1) |S| = Φ:

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

2) |S| = 1:

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

3) |S| = 2:

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

4) |S| = 3:

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

Quindi la soluzione ottimale è 1-2-4-3-1.

Pseudo-codice

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)

Implementazione in C/C++

Ecco l'implementazione in C++. La versione seguente corregge l'inizio della sorgente return bug, che ritornava dopo la primissima permutazione invece di enumerare tutti i tour.

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

Produzione:

80

implementazione in Python

Migliori Python l'implementazione rispecchia l' C++ versione. Corregge la sorgente from itertools, import errore di battitura, la virgola fuori posto return all'interno del circuito interno e l'incavo fuori posto su 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))

Produzione:

80

Soluzioni accademiche al TSP

Gli informatici hanno trascorso decenni alla ricerca di algoritmi a tempo polinomiale migliorati per il problema del commesso viaggiatore. Finora, il problema del commesso viaggiatore rimane NP-difficile.

Diverse tecniche pubblicate riducono la complessità pratica per specifiche famiglie di istanze del problema del commesso viaggiatore (TSP):

• Il TSP simmetrico classico viene risolto dal Metodo del suffisso zero.
• Migliori Algoritmo di ottimizzazione basato sulla biogeografia Utilizza strategie di migrazione per risolvere problemi di ottimizzazione che corrispondono al problema del commesso viaggiatore (TSP).
• Migliori Algoritmo evolutivo multi-obiettivo È progettato per il problema del commesso viaggiatore multi-obiettivo e si basa su NSGA-II.
• Migliori Sistema multi-agente Questo approccio risolve il problema del commesso viaggiatore (TSP) per N città con risorse computazionali fisse.
• Migliori Euristica di Lin-Kernighan e il suo successore LKH fornire tour con una precisione del 2-3% rispetto all'ottimale per casi con milioni di città.
• Concordia Utilizza piani di taglio e l'algoritmo branch-and-cut per calcolare gli ottimi esatti per istanze di benchmark con decine di migliaia di città.

Applicazione del problema del commesso viaggiatore

Il problema del commesso viaggiatore si presenta nel mondo reale sia in forma pura che modificata. Alcune delle principali applicazioni sono:

• Pianificazione, logistica e produzione di microchip: I problemi di inserimento dei chip nell'industria dei microchip vengono modellati come varianti del problema del commesso viaggiatore (TSP) per minimizzare il tempo di spostamento del braccio robotico.
• Sequenziamento del DNA: Un TSP modificato viene utilizzato nel sequenziamento del DNA, dove le città rappresentano i frammenti di DNA e le distanze rappresentano la similarità tra i frammenti.
• Astronomia: Gli astronomi utilizzano il TSP per ridurre al minimo il tempo impiegato per spostare i telescopi tra gli obiettivi di osservazione.
• Controllo ottimale: Le formulazioni TSP modellano problemi di controllo ottimo in cui è necessario rispettare molteplici vincoli, minimizzando al contempo il costo di attraversamento.
• Consegna dell'ultimo miglio: AmazonUPS e le app di consegna di cibo risolvono le varianti dinamiche del TSP per sequenziare le fermate per gli autisti.
• Prelievo in magazzino: Robot e operatori umani seguono percorsi ottimizzati dal sistema TSP (Total Service Provider) che riducono i tempi di spostamento all'interno dei centri di distribuzione.

Analisi della complessità del TSP

• Complessità temporale: L'approccio di programmazione dinamica Held-Karp risolve 2^N sottoinsiemi per ogni nodo iniziale, dando N × 2^N sottoproblemi. Ogni sottoproblema richiede un tempo lineare per essere combinato. Se il nodo di origine non è specificato, è necessario un ciclo esterno su N nodi. La complessità temporale totale è O(N² × 2^N).
• Complessità spaziale: La tabella DP memorizza C(S, i) per ogni sottoinsieme S dell'insieme dei vertici. Ce ne sono 2^N sottoinsiemi per nodo, quindi la complessità dello spazio è O(N × 2^N), che spesso viene scritto come O(2^N) quando N viene considerato fisso.

Successivamente, scopri il Algoritmo del crivello di Eratostene.

DOMANDE FREQUENTI