Non molto tempo fa, un team di ricercatori delle università di Stanford e McGill ha battuto un record di 35 anni in informatica con un margine quasi impercettibile-quattro centesimi di un trilionesimo di un trilionesimo di un trilionesimo di un trilionesimo di un, L’anticipo-fatto a quel bambino poster per dilemmi informatici difficili da risolvere, il problema del “venditore ambulante” – era troppo minuscolo per avere un significato pratico immediato, ma ha dato nuova vita alla ricerca di soluzioni approssimative migliorate.

*Storia originale ristampata con il permesso di Simons Science News, una divisione editorialmente indipendente di SimonsFoundation.org la cui missione è migliorare la comprensione pubblica della scienza coprendo gli sviluppi e le tendenze della ricerca in matematica e nelle scienze computazionali, fisiche e della vita.,* Il problema del commesso viaggiatore si chiede: data una raccolta di città collegate da autostrade, qual è il percorso più breve che visita ogni città e ritorna al luogo di partenza? La risposta ha applicazioni pratiche a processi come fori di perforazione in circuiti stampati, compiti di pianificazione su un computer e ordinare le caratteristiche di un genoma.

Visualizza altro

Il problema del commesso viaggiatore è facile da dichiarare e — almeno in teoria — può essere facilmente risolto controllando ogni percorso di andata e ritorno per trovare quello più breve., Il problema con questo approccio di forza bruta è che man mano che il numero di città cresce, il numero corrispondente di round-trip da controllare supera rapidamente le capacità dei computer più veloci. Con 10 città, ci sono più di 300.000 diversi andata e ritorno__.__ Con 15 città, il numero di possibilità palloncini a più di 87 miliardi.,

L’algoritmo di Christofides

Nei primi giorni dei computer, i matematici speravano che qualcuno avrebbe trovato un approccio molto migliore ai grandi problemi dei venditori ambulanti — un algoritmo che consentisse ai computer di risolverli in un ragionevole lasso di tempo. Ma mentre gli scienziati informatici hanno fatto progressi con scenari specifici-identificando il percorso di andata e ritorno più breve per _ _ una mappa di 49 città negli anni ’50, una mappa di 2.392 città negli anni’ 80 e una mappa di 85.900 città nel 2006-nessuno ha ideato un algoritmo in grado di risolvere in modo efficiente ogni problema di commesso viaggiatore., Secondo un articolo storico pubblicato nel 1972, una tale soluzione potrebbe anche non essere possibile. Lo scienziato informatico Richard Karp, dell’Università della California a Berkeley, __ha dimostrato che il problema del commesso viaggiatore è “NP-difficile”, il che significa che non ha un algoritmo efficiente (a meno che una famosa congettura chiamata P=NP sia vera — ma la maggior parte degli informatici ora sospetta che sia falsa).

Dopo Karp il documento è stato pubblicato, computer di molti scienziati hanno messo gli occhi sulla creazione di un algoritmo efficiente per trovare soluzioni approssimate per il problema del commesso viaggiatore — round-trip percorsi le cui lunghezze venire all’interno della distanza notevole di quella del miglior percorso possibile., Qui, hanno avuto più fortuna: Nel 1976, Nicos Christofides, professore all’Imperial College di Londra, ha sviluppato un algoritmoche produce percorsi garantiti per essere al massimo il 50 per cento più lungo del percorso più breve.

Quando è stato creato, molti informatici presumevano che l’algoritmo di Christofides, che è abbastanza semplice da insegnare agli studenti di informatica in un’ora, fosse un segnaposto che alla fine avrebbe lasciato il posto a un algoritmo più sofisticato in grado di approssimare meglio la vera soluzione. Eppure per decenni, quell’algoritmo non è riuscito a materializzarsi.,

“Quasi tutti gli studenti laureati in informatica teorica hanno trascorso alcune settimane o mesi inutili cercando di migliorare l’algoritmo di Christofides”, ha detto Sanjeev Arora, informatico dell’Università di Princeton.

Infine, nel 2011, il team di Stanford-McGill ha superato la garanzia del 50% di Christofides per alcuni tipi di problemi di venditori ambulanti, dimostrando che le soluzioni del suo algoritmo sarebbero al massimo 49.999999999999999999999999999999999999999999999999996 per cento più lungo della vera risposta.,

Da allora è emersa una serie di algoritmi di approssimazione migliorati, dopo che gli informatici hanno iniziato a guardare il problema con occhi nuovi. Sebbene queste approssimazioni si applichino solo a determinati tipi di problemi di venditori ambulanti, l’approccio che incarnano è molto promettente, ha affermato Michel Goemans, informatico del Massachusetts Institute of Technology.

“Abbiamo appena graffiato la superficie”, ha detto. “Sono un grande credente che, forse cinque anni lungo la strada, ci sarà un risultato molto più potente.,”

L’albero più corto

L’algoritmo di Christofides inizia cercando non il percorso di andata e ritorno più breve, ma il più breve” spanning tree ” -una raccolta di rami che collegano le città, senza anelli chiusi. A differenza del percorso di andata e ritorno più breve, l’albero di spanning più breve è facile da costruire in modo efficiente: inizia trovando l’autostrada più breve che collega due città; questo è il primo ramo. Per aggiungere il ramo successivo, trovare l’autostrada più breve che collega una nuova città a una di queste due — e così via fino a quando tutte le città sono state raggiunte.,

L’albero risultante non è una possibile soluzione al problema del commesso viaggiatore perché non crea un percorso di andata e ritorno. Ma può essere convertito in un viaggio di andata e ritorno visualizzando i rami come muri e poi immaginando di camminare lungo l’albero, con il dito che tocca il muro, fino a tornare al punto in cui hai iniziato. Il viaggio risultante visita ogni città e ritorna al punto di partenza, ma di solito è lontano dal modo più breve per farlo perché in genere comporta passi ripercorrendo molte volte — ogni muro nell’albero viene attraversato due volte, una volta su ciascun lato.,

Tuttavia, questo percorso di andata e ritorno è, nel peggiore dei casi, il doppio della migliore soluzione al problema del commesso viaggiatore. Aggiungendo alcune autostrade scelte con cura a questo albero e prendendo alcune scorciatoie intelligenti, Christofides ha mostrato come tagliare questo andata e ritorno a uno che è al massimo 50 per cento più lungo del percorso più breve.

Il più breve spanning tree è stato un punto di partenza naturale per gli sforzi per costruire un breve tour di andata e ritorno., Ma questo approccio ha anche offerto un’apertura per i ricercatori che cercavano di ridurre la garanzia del 50% di Christofides. Per anche se il più breve spanning tree sembra efficace in un primo momento, altri alberi possono essere meglio quando si tratta di processo di taglio corto che converte l’albero in un round-trip-per esempio, un albero che non rami ha bisogno di una sola autostrada aggiunto per diventare un round — trip.

Quindi l’obiettivo era trovare un albero di spanning che raggiungesse il perfetto equilibrio tra lunghezza e facile conversione in un round-trip., Nessun algoritmo efficiente può scoprire questo albero perfetto (a meno che P=NP), ma un algoritmo di approssimazione di successo deve solo trovarne uno abbastanza buono.

Un Frazionale Viaggio

Il percorso verso quel “abbastanza buono” spanning tree ha coinvolto ampiamente utilizzato, ma controintuitivo tecnica di consentire frazionaria soluzioni a certi tipi di problemi. Un andata e ritorno frazionario, per esempio, potrebbe coinvolgere andando su metà dell’autostrada da Minneapolis a Detroit e metà dell’autostrada da Cleveland a Detroit. Un tale percorso è, ovviamente, un’assurdità dal punto di vista pratico., Ma può essere formulato in termini matematici precisi e, a differenza del problema del venditore ambulante standard, questa versione frazionaria può essere risolta in modo efficiente.

Molti problemi di approssimazione in informatica possono essere affrontati calcolando la soluzione alla versione frazionaria del problema e quindi trovando un modo intelligente per arrotondare le frazioni per produrre una soluzione approssimativa al problema originale. Ma fino a poco tempo fa, nessuno aveva capito un buon modo per farlo per il problema commesso viaggiatore.,

Nel 2009, Amin Saberi della Stanford University e Arash Asadpour, allora studente laureato, hanno sviluppato una tecnica di arrotondamento generale che utilizza la casualità per cercare di scegliere una soluzione a numero intero che conserva il maggior numero possibile di proprietà della soluzione frazionaria. Saberi ha visto questa nuova tecnica di arrotondamento come “un forte martello alla ricerca di un chiodo.”Il chiodo giusto, sospettava, potrebbe essere il problema del venditore ambulante.,

Un paio di mesi più tardi, Saberi, Asadpour, Goemans, la Stanford graduate student Shayan Gharan, e Aleksander Madry, ora dell’École Polytechnique Fédérale di Losanna, in Svizzera, ha mostrato che la nuova modalità di arrotondamento tecnica in grado di produrre una buona approssimazione dell’algoritmo per una variante del problema del commesso viaggiatore, il “asimmetrico” caso. L’anno successivo, Saberi, Gharan e Mohit Singh della McGill University utilizzato lo stesso approccio per sviluppare un nuovo algoritmo di approssimazione per il problema ordinario commesso viaggiatore.,

Data una mappa di città e autostrade, il nuovo algoritmo inizia calcolando l’esatta soluzione frazionaria al problema del commesso viaggiatore. Successivamente, completa quella soluzione frazionaria a un albero che si spera si avvicini a colpire il ricercato equilibrio tra lunghezza e facile conversione in un round-trip. Infine, l’algoritmo inserisce l’albero di spanning-piuttosto che l’albero di spanning più breve — nel framework di Christofides.

Il nuovo algoritmo era “un’idea che potremmo descrivere in un’ora o due, ma dimostrare che ha effettivamente funzionato ha richiesto più di un anno”, ha detto Saberi.,

Dopo una lunga analisi, il team di Stanford-McGill è stato finalmente in grado di battere l’algoritmo di Christofides con un piccolo margine per problemi di venditori itineranti “grafici”, un’ampia sottoclasse. In pochi mesi, altri gruppi, stimolati dal successo del team di Stanford-McGill, hanno utilizzato altre tecniche di arrotondamento per produrre algoritmi per il caso grafico con approssimazioni migliori; il record attuale si attesta al 40%, un miglioramento sostanziale rispetto al 50% di Christofides.,

Il caso grafico “incapsula molte delle stesse difficoltà che si incontrano nel problema generale”, ha detto Arora, aggiungendo che le stesse tecniche che funzionano per il caso grafico potrebbero essere portate a sopportare il problema generale del commesso viaggiatore.

Tuttavia, Saberi ha detto, risolvere il problema di approssimazione commesso viaggiatore nella sua piena generalità probabilmente richiederà un infuso di nuove idee.,

“La scoperta matematica è come sentirsi in una stanza buia: mettere la mano qui e trovare una sedia, mettere la mano lì e trovare un tavolo”, ha detto, parafrasando il matematico Andrew Wiles. “Ad un certo punto, la tua mano colpisce l’interruttore della luce e improvvisamente tutto ha senso. Per il problema del commesso viaggiatore, anche dopo così tanti documenti che hanno spinto la busta in così tante direzioni, non penso che abbiamo ancora colpito quell’interruttore.”

Storia originale ristampata con il permesso di Simons Science News, una divisione editorialmente indipendente di SimonsFoundation.,org la cui missione è quella di migliorare la comprensione pubblica della scienza coprendo gli sviluppi della ricerca e le tendenze in matematica e le scienze computazionali, fisiche e della vita.