Problema del commesso viaggiatore: Python, C++ Algoritmo

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

Il problema del commesso viaggiatore (TSP) è un classico problema combinatorio dell'informatica teorica. Il problema chiede di trovare il percorso più breve in un grafo con la condizione di visitare tutti i nodi una sola volta e ritornare alla città di origine.

La dichiarazione del problema fornisce un elenco di città insieme alle distanze tra ciascuna città.

Obiettivo: Per iniziare dalla città di origine, visita le altre città una sola volta e torna nuovamente alla città di origine. Il nostro obiettivo è trovare il percorso più breve possibile per completare il percorso di andata e ritorno.

Esempio di TSP

Qui viene fornito un grafico in cui 1, 2, 3 e 4 rappresentano le città e il peso associato a ciascun bordo rappresenta la distanza tra tali città.

L'obiettivo è trovare il percorso più breve possibile per il tour che parte dalla città di origine, attraversa il grafico visitando le altre città o nodi una sola volta e ritorna alla città di origine.

Per il grafico sopra, il percorso ottimale è seguire il percorso del costo minimo: 1-2-4-3-1. E questo percorso più breve costerebbe 10+25+30+15 =80

Soluzioni diverse al problema del commesso viaggiatore

Il problema del commesso viaggiatore (TSP) è classificato come un problema NP-difficile perché non ha un algoritmo in tempo polinomiale. La complessità aumenta esponenzialmente aumentando il numero di città.

Esistono diversi modi per risolvere il problema del commesso viaggiatore (cucchiaino). Alcune soluzioni popolari sono:

L’approccio della forza bruta è il metodo ingenuo per risolvere i problemi dei venditori ambulanti. In questo approccio, prima calcoliamo tutti i percorsi possibili e poi li confrontiamo. Il numero di percorsi in un grafico composto da n città è n! Risolvere il problema del commesso viaggiatore con questo approccio basato sulla forza bruta è molto costoso dal punto di vista computazionale.

Il metodo branch-and-bound: In questo approccio il problema viene suddiviso in sottoproblemi. La soluzione di questi singoli sottoproblemi fornirebbe una soluzione ottimale.

Questo tutorial dimostrerà un approccio di programmazione dinamica, la versione ricorsiva di questo metodo branch-and-bound, per risolvere il problema del venditore ambulante.

Programmazione dinamica è un metodo per cercare soluzioni ottimali analizzando tutti i percorsi possibili. È uno dei metodi di soluzione esatta che risolve i problemi dei venditori ambulanti a costi relativamente più elevati rispetto a quelli del venditore ambulante metodi avidi che forniscono una soluzione quasi ottimale.

La complessità computazionale di questo approccio è O(N^2 * 2^N) di cui si parlerà più avanti in questo articolo.

Il metodo del vicino più prossimo è un approccio greedy basato su euristiche in cui scegliamo il nodo vicino più vicino. Questo approccio è computazionalmente meno costoso dell'approccio dinamico. Ma non fornisce la garanzia di una soluzione ottimale. Questo metodo è utilizzato per soluzioni quasi ottimali.

Algoritmo per il problema del commesso viaggiatore

Utilizzeremo l'approccio di programmazione dinamica per risolvere il problema del commesso viaggiatore (TSP).

Prima di iniziare l'algoritmo, familiarizziamo con alcune terminologie:

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

Supponiamo che S sia il sottoinsieme delle città e appartenga a {1, 2, 3, …, n} dove 1, 2, 3…n sono le città e i, j sono due città in quel sottoinsieme. Ora cost(i, S, j) è definito in modo tale come la lunghezza del percorso più breve che visita il nodo in S, che esattamente una volta ha il punto iniziale e finale rispettivamente come i e j.

Ad esempio, il costo (1, {2, 3, 4}, 1) denota la lunghezza del percorso più breve dove:

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

L'algoritmo di programmazione dinamica sarebbe:

• Imposta costo(i, , i) = 0, il che significa che iniziamo e finiamo da i e il costo è 0.
• Quando |S| > 1, definiamo costo(i, S, 1) = ∝ dove i !=1 . Perché inizialmente non conosciamo il costo esatto per raggiungere la città i fino alla città 1 attraverso altre città.
• Ora dobbiamo iniziare da 1 e completare il tour. Dobbiamo selezionare la città successiva in questo modo-

costo(i, S, j)=costo minimo (i, S−{i}, j)+dist(i,j) dove i∈S e i≠j

Per la figura data, la matrice di adiacenza sarebbe la seguente:

dist(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

Vediamo come funziona il nostro algoritmo:

Passo 1) Stiamo considerando il nostro viaggio partendo dalla città 1, visitando altre città una volta e tornando alla città 1.

Passo 2) S è il sottoinsieme delle città. Secondo il nostro algoritmo, per tutti i |S| > 1, imposteremo la distanza cost(i, S, 1) = ∝. Qui cost(i, S, j) significa che stiamo iniziando dalla città i, visitando le città di S una volta, e ora siamo nella città j. Impostiamo questo costo del percorso come infinito perché non conosciamo ancora la distanza. Quindi i valori saranno i seguenti:

Costo (2, {3, 4}, 1) = ∝ ; la notazione indica che stiamo iniziando dalla città 2, attraversando le città 3, 4 e raggiungendo 1. E il costo del percorso è infinito. Allo stesso modo-

costo(3, {2, 4}, 1) = ∝

costo(4, {2, 3}, 1) = ∝

Passo 3) Ora, per tutti i sottoinsiemi di S, dobbiamo trovare quanto segue:

costo(i, S, j)=costo minimo (i, S−{i}, j)+dist(i,j), dove j∈S e i≠j

Ciò significa il percorso di costo minimo per iniziare da i, attraversare una volta il sottoinsieme di città e tornare alla città j. Considerando che il viaggio inizia nella città 1, il costo del percorso ottimale sarebbe= costo(1, {altre città}, 1).

Scopriamo come potremmo raggiungere questo obiettivo:

Ora S = {1, 2, 3, 4}. Ci sono quattro elementi. Quindi il numero di sottoinsiemi sarà 2 ^ 4 o 16. Questi sottoinsiemi sono-

1) |S| = Nullo:

{Φ}

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

Dato che iniziamo da 1, potremmo scartare i sottoinsiemi contenenti la città 1.

Il calcolo dell'algoritmo:

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 sarebbe 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 Є 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) 

Implementazione in C/C++

Ecco l'implementazione in 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;
}

Produzione:

80

implementazione in 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))

Produzione:

80

Soluzioni accademiche al TSP

Gli informatici hanno trascorso anni alla ricerca di un algoritmo polinomiale migliorato per il problema del commesso viaggiatore. Finora, il problema è ancora NP-difficile.

Sebbene negli ultimi anni siano state pubblicate alcune delle seguenti soluzioni che hanno ridotto la complessità in una certa misura:

• Il classico TSP simmetrico viene risolto con il metodo del suffisso zero.
• L’algoritmo di ottimizzazione basato sulla biogeografia si basa sulla strategia di migrazione per risolvere i problemi di ottimizzazione che possono essere pianificati come TSP.
• L'algoritmo evolutivo multi-obiettivo è progettato per risolvere più TSP basati su NSGA-II.
• Il Sistema Multi-Agente risolve il TSP di N città con risorse fisse.

Applicazione del problema del commesso viaggiatore

Il problema del commesso viaggiatore (TSP) viene applicato nel mondo reale sia nella sua forma più pura che modificata. Alcuni di questi sono:

• Pianificazione, logistica e produzione di microchip: I problemi di inserimento dei chip sorgono naturalmente nell'industria dei microchip. Questi problemi possono essere pianificati come problemi del commesso viaggiatore.
• Sequenziamento del DNA: Una leggera modifica del problema del commesso viaggiatore può essere utilizzata nel sequenziamento del DNA. Qui le città rappresentano i frammenti di DNA e la distanza rappresenta la misura di somiglianza tra due frammenti di DNA.
• Astronomia: Il problema del commesso viaggiatore viene applicato dagli astronomi per ridurre al minimo il tempo trascorso a osservare varie sorgenti.
• Problema di controllo ottimo: Venditore ambulante La formulazione del problema può essere applicata a problemi di controllo ottimo. Potrebbero essere aggiunti molti altri vincoli.

Analisi della complessità del TSP

• Complessità temporale: Ce ne sono un totale di 2^N sottoproblemi per ciascun nodo. Quindi il numero totale di sottoproblemi sarebbe N*2^N. Ciascuno dei sottoproblemi richiede tempo lineare per essere risolto. Se il nodo di origine non è specificato, dobbiamo eseguire cicli per N nodi.

  Quindi la complessità temporale totale per una soluzione ottimale sarebbe il numero di nodi * numero di sottoproblemi * tempo per risolvere ogni sottoproblema. La complessità temporale può essere definita come O(N² *2^N).

• Complessità spaziale: L'approccio di programmazione dinamica utilizza la memoria per memorizzare C(S, i), dove S è un sottoinsieme dell'insieme dei vertici. Ce ne sono in totale 2^N sottoinsiemi per ogni nodo. Quindi, la complessità dello spazio è O(2^N).

Successivamente imparerai a conoscere Algoritmo del crivello di Eratostene