Il TSP (traveler salesman problem) è un problema di ricerca operativa/ottimizzazione/teoria dei grafi/informatica teorica

Consiste nel trovare un ciclo Hamiltoniano di costo minimo in un grafo completo. Cosa vuol dire tutto ciò?

Un grafo è un insieme di nodi e vertici che connettono i nodi, nel nostro abbiamo anche un costo associato ad ogni arco.

Nel nostro caso ogni pallina è un nodo, ogni stanghetta che le congiunge è un arco, il numero di persone sui binari è il costo che paghiamo nel passarci sopra.

I grafi si distinguono in orientati e non. Negli orientati il verso dell'arco (da nodo V a nodo W o viceversa) conta e non sempre si può andare in entrambi i versi, mentre nei non orientati ogni arco è percorribile in entrambi i versi.

Nel nostro caso, abbiamo un grafo non orientato.

Un cammino è un insieme ordinato di nodi o, equivalentemente, un insieme sequenziale di archi, cioè l'arco che precede deve avere come nodo di arrivo quello di partenza dell'arco successivo.

Non sempre esiste un arco da un nodo ad un altro e di fatti non sempre in un grafo tutti i cammini sono ammissibili, ma nel nostro caso (del TSP, quello dell'immagine non è completo) il grafo è completo, cioè esiste un arco da un nodo a un altro per ogni coppia di nodi.

Il costo che associamo agli archi lo teniamo in considerazione quando tale arco è nel nostro cammino. Quindi il costo totale di un cammino equivale alla somma dei costi degli archi su cui siamo passati.

Un ciclo Hamiltoniano è un cammino in cui ogni nodo del grafo viene visitato una e una sola volta ed esiste un arco che collega l'ultimo nodo al primo. Da qui la parola ciclo. Immaginatevelo come un poligono tutto spiegazzato. Ovviamente il nostro ciclo Hamiltoniano, per essere tale, deve avere esattamente tanti archi quanto i nodi del nostro grafo.

Come si risolve questo problema? Beh, in realtà è un problema computazionalmente difficile, addirittura NP-hard. Detto informalmente, ciò vuol dire che è tra "più difficili" della classe NP, che sarebbe, prendendo una delle definizioni, la classe dei problemi verificabili in tempo polinomiale da una macchina di Turing deterministica, cioè avendo una soluzione posso verificare che è tale in tempo polinomiale. Mentre la classe P è quella dei problemi per cui una macchina di Turing deterministica può RISOLVERLI in tempo polinomiale. È chiaro che P è contenuto in NP, ma non si sa se è uguale, si congettura che P≠NP. Ancora oggi è uno delle congetture più note e più difficili da risolvere nell'informatica teorica.

Se potessimo risolvere un problema NP-hard in tempo polinomiale potremmo (teoricamente) ricondurre ogni altro problema a questo in tempo polinomiale e in tal modo dimostreremmo che P=NP.

Fare una ricerca esaustiva per il TSP (cioè provare tutti i cammini possibili) è molto problematico, visto che il tempo richiesto per farlo crescerebbe esponenzialmente rispetto al numero di nodi.

Si usano dunque varie tecniche, come l'euristica e algoritmi approssimati, per dare dei bound alla soluzione, cioè restringere il range di valori possibili del costo minimo dando un intervallo in cui potrebbe stare. E dunque da lì è possibile approssimare meglio.

Il discorso su come si può risolvere in questi modi ottimali sarebbe lungo e dispersivo, quindi lo ometterò, anche perché non sono un'esperta dell'argomento e conosco solo 2/3 metodi.

In ogni caso, avere una soluzione esatta in tempo polinomiale ancora non è possibile e probabilmente non lo sarà mai.

Difatti la congettura predonimante ad oggi è che P≠NP e che quindi problemi NP-hard come questo, fino a prova contraria, si pensa che non saranno mai risolvibili in tempo polinomiale.

Per ultimo: a cosa ce ne frega di risolvere in maniera efficiente il TSP? In realtà a tante cose, è un problema di grande interesse, nell'ambito del trasporto ottimale ma in tante altre cose della logistica e ci sono formulazioni differenti e generalizzazioni che comunque conservano il core originale.