Shrinking Blob calcola le soluzioni per i venditori ambulanti

Il problema del commesso viaggiatore è una delle sfide più famose in matematica. Questo è il problema di trovare il percorso più breve per visitare una volta più città e poi tornare al luogo di origine.

Certo, è semplice trovare percorsi che visitino ogni città in questo modo. La grande sfida è trovare il più corto.

C'è un modo sicuro per farlo: con la pura forza bruta. Ciò significa misurare la lunghezza di ogni tour e stabilire quale sia la più breve. Il problema è che questo compito diventa sempre più lungo all'aumentare del numero di città. In effetti, per un gran numero di città, è computazionalmente irrealizzabile.

È facile immaginare che potrebbe esserci una sorta di scorciatoia matematica intelligente che risolve questo problema. Non così. In effetti, i matematici tendono a concordare sul fatto che non si troverà mai una scorciatoia generale (questo è il cosiddetto dibattito P=NP).

Devono invece fare affidamento su processi di ottimizzazione che cercano soluzioni brevi ma non sono in grado di dimostrare che queste siano effettivamente le più brevi.

Quindi la sfida per tutti gli scopi pratici è trovare algoritmi che producono buoni risultati e che siano computazionalmente efficienti.

Oggi Jeff Jones e Andrew Adamatzky dell'Università dell'Inghilterra occidentale nel Regno Unito rivelano un approccio insolito. Questi ragazzi dicono che una soluzione ragionevole può essere trovata rappresentando le città come una serie di punti in una capsula di Petri virtuale, immergendo i punti in una macchia di sostanza appiccicosa virtuale e poi riducendola.

In termini semplificati, il blob si aggrappa ai punti mentre si restringe, collegandoli con una superficie minima, un po' come una superficie di una bolla di sapone. Man mano che il blob si restringe, si adatta morfologicamente alla configurazione delle città, dicono.

Quando tutti i punti si trovano sulla superficie del blob, la superficie risultante è una soluzione al problema del commesso viaggiatore che generalmente è piuttosto buona.

L'ingrediente magico in tutto questo è il goo speciale. Consiste di molte particelle che si muovono ciascuna secondo un insieme di regole semplici, come agenti autonomi. Questi siedono in un mare di chemiotattica, un profumo virtuale a cui le particelle sono attratte. In ogni fase del calcolo, ogni particella rileva il chemioattrattore intorno a sé e quindi si sposta verso la regione di massima concentrazione. Mentre si muove, lascia dietro di sé la propria traccia del chemiotattico affinché altre particelle lo seguano.

Il risultato è una sorta di blob intelligente che mostra un comportamento emergente, come la capacità di ridurre al minimo la sua superficie.

Jones e Adamatzky hanno messo alla prova questo goo intelligente facendogli perdere i problemi dei venditori ambulanti costituiti da 20 città distribuite casualmente in una capsula di Petri virtuale. hanno piazzato video del processo di restringimento qui .

I risultati sono buoni ma non perfetti. Hanno creato 20 diversi scenari di 20 città e hanno eseguito il blob 6 volte su ciascuno. Hanno quindi confrontato il percorso più breve del blob con il percorso più breve effettivo trovato dalla forza bruta. Jones e Adamatzky affermano che se questo percorso più breve è di lunghezza 1, il blob intelligente ha trovato tour con una lunghezza media del tour migliore di 1,04, una lunghezza media del tour di 1,07 e una lunghezza media del tour peggiore di 1,09.

Non è male. Ma il vero vantaggio sta nella semplicità dell'approccio che è essenzialmente emergente e non prevede particolari processi di ottimizzazione. Produce anche una mappa del percorso alla fine (sebbene sia necessaria un'interpretazione umana per dargli un senso).

Ci sono degli svantaggi, ovviamente. Ci sono alcune configurazioni di città che il blob non può affrontare. Questi si verificano quando il percorso più breve forma una sorta di stretto tra due città piuttosto che un collegamento, come lo stretto di Gibilterra tra l'Oceano Atlantico e il Mar Mediterraneo. Invece, il blob tende a connetterli.

Tuttavia, questa è un'interessante forma di calcolo non convenzionale che produce un'affascinante alternativa agli algoritmi convenzionali del commesso viaggiatore. Ha la più stretta somiglianza con gli approcci con l'elastico che circondano le città con un elastico e poi tentano progressivamente di allungare l'elastico per collegare le città all'interno. La grande differenza è che le proprietà del materiale del blob sono emergenti piuttosto che pre-programmate.

Jones e Adamatzky affermano che il prossimo passo sarebbe creare un modello fisico di questo sistema in cui un vero blob fa il lavoro, magari usando la minimizzazione viscoelastica dell'energia libera. Tuttavia, progettare un materiale del genere potrebbe essere complicato.

Un altro approccio, che potrebbe avere un'applicazione più ampia, sarebbe quello di distillare le proprietà di questo calcolo non convenzionale in un algoritmo classico.

La cosa migliore è la prospettiva che i responsabili della logistica pianifichino i percorsi di consegna immergendo i modelli della rete stradale in vasche di sostanza appiccicosa intelligente. Quindi aspetteremo con trepidazione questa nuova scienza dell'alchimia del commesso viaggiatore.

Rif: arxiv.org/abs/1303.4969 : Calcolo del problema del commesso viaggiatore da parte di un blob che si restringe

nascondere