“Questo è un risultato che ho voluto tutta la mia carriera,” ha detto David Williamson, della Cornell University, che ha studiato il viaggio commesso problema dal 1980.
Il viaggio commesso problema è uno di una manciata di fondamentali problemi teorici informatici girare di nuovo e di nuovo a testare i limiti di calcolo efficiente. Il nuovo risultato “è il primo passo per dimostrare che le frontiere del calcolo efficiente sono in realtà migliori di quello che pensavamo”, ha detto Williamson.,
Progresso frazionario
Mentre probabilmente non esiste un metodo efficiente che trovi sempre il viaggio più breve, è possibile trovare qualcosa di quasi altrettanto buono: l’albero più corto che collega tutte le città, ovvero una rete di connessioni (o “bordi”) senza loop chiusi. L’algoritmo di Christofides utilizza questo albero come spina dorsale per un tour di andata e ritorno, aggiungendo bordi aggiuntivi per convertirlo in un viaggio di andata e ritorno.
Qualsiasi percorso di andata e ritorno deve avere un numero pari di bordi in ogni città, poiché ogni arrivo è seguito da una partenza., Si scopre che è vero anche il contrario: se ogni città di una rete ha un numero pari di connessioni, i bordi della rete devono tracciare un viaggio di andata e ritorno.
L’albero più corto che collega tutte le città manca di questa proprietà di uniformità, poiché ogni città alla fine di un ramo ha solo una connessione con un’altra città. Quindi, per trasformare l’albero più corto in un viaggio di andata e ritorno, Christofides (che è morto l’anno scorso) ha trovato il modo migliore per collegare coppie di città che hanno numeri dispari di bordi. Poi ha dimostrato che il viaggio di andata e ritorno risultante non sarà mai più del 50% più lungo del miglior viaggio di andata e ritorno possibile.,
In tal modo, ha ideato forse il più famoso algoritmo di approssimazione in informatica teorica — uno che di solito costituisce il primo esempio nei libri di testo e corsi.
“Tutti conoscono il semplice algoritmo”, ha detto Alantha Newman dell’Università di Grenoble Alpes e del Centro Nazionale per la ricerca scientifica in Francia. E quando lo sai, ha detto, ” conosci lo stato dell’arte” — almeno, lo hai fatto fino allo scorso luglio.
Gli informatici hanno a lungo sospettato che ci dovrebbe essere un algoritmo di approssimazione che supera l’algoritmo di Christofides., Dopo tutto, il suo algoritmo semplice e intuitivo non è sempre un modo così efficace per progettare un percorso di vendita itinerante, dal momento che l’albero più corto che collega le città potrebbe non essere la migliore spina dorsale che si possa scegliere. Ad esempio, se questo albero ha molti rami, ogni città alla fine di un ramo dovrà essere abbinata a un’altra città, formando potenzialmente molte nuove costose connessioni.,
Nel 2010, Oveis Gharan, Saberi e Mohit Singh del Georgia Institute of Technology hanno iniziato a chiedersi se fosse possibile migliorare l’algoritmo di Christofides scegliendo non l’albero più corto che collega tutte le città, ma un albero casuale da una collezione accuratamente scelta. Hanno preso ispirazione da una versione alternativa del problema venditore itinerante in cui si è permesso di viaggiare lungo una combinazione di percorsi — forse si arriva a Denver via 3/4 del percorso da Chicago a Denver più 1/4 del percorso da Los Angeles a Denver.,
A differenza del normale problema del commesso viaggiatore, questo problema frazionario può essere risolto in modo efficiente. E mentre i percorsi frazionari non hanno senso fisico, gli scienziati informatici hanno a lungo creduto che il miglior percorso frazionario dovrebbe essere una guida approssimativa ai contorni di buoni percorsi ordinari.
Quindi, per creare il loro algoritmo, Oveis Gharan, Saberi e Singh hanno definito un processo casuale che sceglie un albero che collega tutte le città, in modo che la probabilità che un dato bordo sia nell’albero sia uguale alla frazione di quel bordo nel miglior percorso frazionario., Ci sono molti processi casuali, quindi i ricercatori ne hanno scelto uno che tende a produrre alberi con molte città collegate in modo uniforme. Dopo che questo processo casuale sputa un albero specifico, il loro algoritmo lo inserisce nello schema di Christofides per abbinare le città con numeri dispari di bordi, per convertirlo in un viaggio di andata e ritorno.
Questo metodo sembrava promettente, non solo per i tre ricercatori, ma per altri scienziati informatici. ” L’intuizione è semplice”, ha detto Ol Svensson dell’Istituto federale svizzero di tecnologia di Losanna. Ma ” per dimostrare che si rivela essere una bestia diversa.,”
L’anno seguente, però, Oveis Gharan, Saberi e Singh è riuscito a dimostrare che il loro algoritmo batte Christofides’ algoritmo per la “grafica” in viaggio commesso problemi — quelli in cui le distanze tra le città sono rappresentate da una rete (non necessariamente tutte le connessioni) in cui ogni bordo ha la stessa lunghezza. Ma i ricercatori non sono riusciti a capire come estendere il loro risultato al problema generale del venditore ambulante, in cui alcuni bordi potrebbero essere molto più lunghi di altri.,
“Se dobbiamo aggiungere un vantaggio super costoso alla corrispondenza, allora siamo fottuti, fondamentalmente”, ha detto Karlin.
Spingendo indietro
Tuttavia, Oveis Gharan è emerso da quella collaborazione con una convinzione incrollabile che il loro algoritmo dovrebbe battere l’algoritmo di Christofides per il problema generale del commesso viaggiatore. ” Non ho mai avuto dubbi”, ha detto.
Oveis Gharan ha continuato a trasformare il problema nella sua mente negli anni che seguirono., Sospettava che una disciplina matematica chiamata geometria dei polinomi, poco conosciuta nel mondo teorico dell’informatica, potesse avere gli strumenti di cui aveva bisogno. Così, quando Karlin è venuto da lui due anni fa suggerendo che co-consigliare un brillante nuovo studente laureato di nome Nathan Klein che aveva doppia specializzazione in matematica e violoncello, ha detto, ” OK, facciamo un tentativo-Ho questo problema interessante.”
Karlin pensava che, se non altro, sarebbe stata una divertente opportunità per saperne di più sulla geometria dei polinomi., “Non pensavo davvero che saremmo stati in grado di risolvere questo problema”, ha detto.
Lei e Oveis Gharan non hanno esitato a lanciare Klein nella parte più profonda della ricerca informatica. Oveis Gharan si era tagliato i denti sul problema del commesso viaggiatore come studente laureato nel 2010. E i due consulenti hanno concordato sui meriti di assegnare problemi difficili agli studenti laureati, specialmente durante i loro primi due anni, quando non sono sotto pressione per ottenere risultati.
I tre si tuffarono in un’intensa collaborazione., ” È tutto ciò a cui stavo pensando per due anni”, ha detto Klein.
Hanno trascorso il primo anno a risolvere una versione semplificata del problema, per avere un’idea delle sfide che stavano affrontando. Ma anche dopo averlo realizzato, il caso generale sembrava ancora un “moonshot”, ha detto Klein.
Tuttavia, avevano avuto un’idea dei loro strumenti — in particolare, la geometria dei polinomi. Un polinomio è una combinazione di termini fatti di numeri e variabili sollevate a potenze, come 3x2y + 8xz7., Per studiare il problema del commesso viaggiatore, i ricercatori hanno distillato una mappa delle città in un polinomio che aveva una variabile per ogni bordo tra le città e un termine per ogni albero che poteva collegare tutte le città. I fattori numerici hanno quindi ponderato questi termini per riflettere il valore di ciascun bordo nella soluzione frazionaria al problema del venditore ambulante.
Questo polinomio, hanno scoperto, ha una proprietà ambita chiamata “stabilità reale”, il che significa che i numeri complessi che fanno valutare il polinomio a zero non si trovano mai nella metà superiore del piano complesso., La cosa bella della stabilità reale è che rimane in vigore anche quando si apportano molti tipi di modifiche al polinomio. Quindi, per esempio, se i ricercatori volessero concentrarsi su città particolari, potrebbero usare una singola variabile per rappresentare tutti i diversi bordi che portano in una città, e potrebbero impostare le variabili per i bordi che non gli interessavano uguali a 1. Man mano che manipolavano questi polinomi semplificati, i risultati delle loro manipolazioni avevano ancora una reale stabilità, aprendo la porta a un vasto assortimento di tecniche.,
Questo approccio ha permesso ai ricercatori di ottenere una maniglia su domande come la frequenza con cui l’algoritmo sarebbe stato costretto a collegare due città lontane. In un’analisi di quasi 80 pagine, sono riusciti a dimostrare che l’algoritmo batte l’algoritmo di Christofides per il problema generale del commesso viaggiatore (il documento deve ancora essere peer-reviewed, ma gli esperti sono fiduciosi che sia corretto). Una volta che la carta è stata completata, Oveis Gharan tratteggiato fuori una e-mail a Saberi, il suo vecchio consulente di dottorato. “Credo di poter finalmente laurearmi”, ha scherzato.
