Nu cu mult timp în urmă, o echipă de cercetători de la Stanford și universitățile McGill a rupt-o de 35 de ani, înregistrați în informatică de către un aproape imperceptibil marja — patru sutimi de o trilionime de trilionime de trilionime de trilionime de procente, pentru a fi exact., Avansul — a făcut pentru că copilul poster pentru greu-de-rezolva informatică dileme, a „comis-voiajor” problemă — a fost prea minuscul pentru a avea orice semnificație practică imediată, dar nu a suflat viață nouă în căutare pentru îmbunătățirea soluții aproximative.

*poveste Originală retipărit cu permisiunea de la Simons Science News, un editorial independent divizia de SimonsFoundation.org a cărei misiune este de a spori înțelegerea publică a științei prin acoperirea cercetare evoluții și tendințe în matematică și computațională, fizică și științele vieții.,* Problema vânzătorului călător întreabă: având în vedere o colecție de orașe conectate prin autostrăzi, care este cea mai scurtă rută care vizitează fiecare oraș și se întoarce la locul de plecare? Răspunsul are aplicații practice la procese, cum ar fi găurirea găurilor în plăcile de circuit, programarea sarcinilor pe un computer și comandarea caracteristicilor unui genom.

Vezi mai mult

problema comis-voiajorului este ușor pentru stat, și — cel puțin în teorie — că pot fi rezolvate cu ușurință prin verificarea fiecărui tur-retur traseu pentru a găsi cea mai scurtă., Problema cu această abordare a forței brute este că, pe măsură ce numărul orașelor crește, numărul corespunzător de călătorii dus-întors pentru a verifica depășește rapid capacitățile celor mai rapide computere. Cu 10 orașe, există mai mult de 300.000 de călătorii dus-întors diferite__.__ Cu 15 orașe, Numărul de posibilități baloane la mai mult 87 miliard.,

Christofides Algoritmul lui

În primele zile de calculatoare, matematicieni sperat că cineva va veni cu o abordare mult mai bine la mare comis-voiajor probleme — unele algoritm care ar permite calculatoarelor să le rezolve într-un interval de timp rezonabil. Dar în timp ce oamenii de stiinta de calculator au făcut progrese cu scenarii specifice — identificarea în cel mai scurt tur-retur traseu pentru__ 49-hartă a orașului în anii 1950, un 2392 de-hartă a orașului în anii 1980 și o 85,900-hartă a orașului în 2006 nimeni nu s — a conceput un algoritm care poate în mod eficient pentru a rezolva fiecare problema comis-voiajor., Potrivit unui document de referință publicat în 1972, o astfel de soluție ar putea nici măcar să nu fie posibilă. Informaticianul Richard Karp, de la Universitatea California din Berkeley, a arătat că problema vânzătorului călător este „NP-hard”, ceea ce înseamnă că nu are un algoritm eficient (cu excepția cazului în care o presupunere faimoasă numită P=NP este adevărată — dar majoritatea Informaticienilor suspectează acum că este falsă).

După Karp ziarul a fost publicat, mulți oameni de știință de calculator pus ochii pe crearea unui algoritm eficient de a găsi soluții aproximative pentru problema comis-voiajorului — tur-retur rute ale căror lungimi veni la distanță mică față de cea a celui mai bun traseu posibil., Aici, ei au avut mai mult noroc: În 1976, Nicos Christofides, profesor la Imperial College din Londra, a dezvoltat o algorithmthat produce rute garantat să fie de cel mult 50 la sută mai mult decât cea mai scurtă rută.când a fost creat, mulți informaticieni au presupus că algoritmul lui Christofides, care este suficient de simplu pentru a preda studenților de informatică într-o oră, a fost un substituent care ar da în cele din urmă loc unui algoritm mai sofisticat capabil să aproximeze mai bine soluția adevărată. Cu toate acestea, de zeci de ani, acest algoritm nu a reușit să se materializeze.,

„aproape fiecare student absolvent în Informatică Teoretică a petrecut la un moment dat câteva săptămâni sau luni inutile încercând să îmbunătățească algoritmul lui Christofides”, a spus Sanjeev Arora, informatician la Universitatea Princeton.

în cele din Urmă, în 2011, la Stanford-McGill echipa tivita trecut Christofides’ 50 la sută de garantare pentru anumite tipuri de comis-voiajor probleme, arată că algoritmul soluții ar fi, cel mult 49.99999999999999999999999999999999999999999999999996 la sută mai mult decât răspunsul adevărat.,un șir de algoritmi de aproximare îmbunătățite au apărut de atunci, după ce oamenii de știință de calculator au început să privească problema cu ochi proaspeți. Deși aceste aproximări se aplică numai anumitor tipuri de probleme de vânzător de călătorie, abordarea pe care o întruchipează are o mare promisiune, a declarat Michel Goemans, informatician la Institutul de Tehnologie din Massachusetts.

„abia am zgâriat suprafața”, a spus el. „Sunt un mare credincios că, poate cinci ani pe drum, va exista un rezultat mult mai puternic.,algoritmul lui Christofides începe prin a căuta nu cea mai scurtă rută dus-întors, ci cea mai scurtă „spanning tree” — o colecție de ramuri care leagă orașele, fără bucle închise. Spre deosebire de cel mai scurt traseu dus-întors, cel mai scurt arbore este ușor de construit eficient: începeți prin a găsi cea mai scurtă autostradă care leagă două orașe; aceasta este prima ramură. Pentru a adăuga următoarea ramură, găsiți cea mai scurtă autostradă care leagă un oraș nou de unul dintre cele două — și așa mai departe până când toate orașele au fost atinse.,arborele rezultat nu este o soluție posibilă la problema vânzătorului călător, deoarece nu creează un traseu dus-întors. Dar poate fi transformat într-o călătorie dus-întors prin vizualizarea ramurilor ca pereți și apoi imaginarea mersului de-a lungul copacului, cu degetul atingând peretele, până când vă întoarceți de unde ați început. Călătoria rezultată vizitează fiecare oraș și se întoarce la punctul de plecare, dar de obicei este departe de cea mai scurtă cale de a face acest lucru, deoarece implică de obicei retragerea pașilor de mai multe ori — fiecare perete din copac este traversat de două ori, o dată pe fiecare parte.,

cu toate Acestea, acest tur-retur traseul este, în cel mai rău, de două ori la fel de mult ca cea mai bună soluție pentru problema comis-voiajorului. Adăugând câteva autostrăzi alese cu grijă în acest copac și luând câteva scurtături inteligente, Christofides a arătat cum să tăiați această călătorie dus-întors la una care este cu cel mult 50 la sută mai lungă decât cea mai scurtă rută.

cel mai scurt copac a fost un punct de plecare natural pentru eforturile de a construi un tur dus-întors scurt., Dar această abordare a oferit, de asemenea, o deschidere pentru cercetătorii care încearcă să reducă garanția de 50% a lui Christofides. Pentru că, deși cel mai scurt spanning tree pare eficiente la început, copaci pot fi mai bine atunci când vine vorba de scurt de tăiere proces care convertește copac într-o tur-retur — de exemplu, un copac ce-n ramuri are nevoie de un singur adăugat autostrada pentru a deveni un tur-retur.deci, scopul a fost de a găsi un copac se întinde care atinge echilibrul perfect între lungime și ușor de conversie într-un dus-întors., Niciun algoritm eficient nu poate descoperi acest arbore perfect (cu excepția cazului în care P=NP), dar un algoritm de aproximare de succes trebuie doar să găsească unul destul de bun.

O Fracționare Excursie

calea spre acel „destul de bun” spanning tree-a implicat utilizate pe scară largă, dar contraintuitiv tehnica de a permite fracționată soluții pentru anumite tipuri de probleme. O călătorie dus-întors fracționată, de exemplu, ar putea implica trecerea pe jumătate de autostradă de la Minneapolis la Detroit și jumătate de autostradă de la Cleveland la Detroit. Un astfel de traseu este, desigur, nonsens dintr-o perspectivă practică., Dar poate fi formulată în termeni matematici preciși și, spre deosebire de problema standard a vânzătorului de călătorie, această versiune fracționată poate fi rezolvată eficient.multe probleme de aproximare în informatică pot fi abordate prin calcularea soluției la versiunea fracționată a problemei și apoi găsirea unui mod inteligent de a rotunji fracțiunile pentru a produce o soluție aproximativă la problema inițială. Dar până de curând, nimeni nu și-a dat seama de o modalitate bună de a face acest lucru pentru problema vânzătorului călător.,în 2009, Amin Saberi de la Universitatea Stanford și Arash Asadpour, apoi student absolvent, au dezvoltat o tehnică generală de rotunjire care folosește aleatorie pentru a încerca să aleagă o soluție cu număr întreg care păstrează cât mai multe proprietăți ale soluției fracționate. Saberi a văzut această nouă tehnică de rotunjire ca „un ciocan puternic în căutarea unui cui.”Unghia dreaptă, bănuia el, ar putea fi problema vânzătorului călător.,

câteva luni mai târziu, Saberi, Asadpour, Goemans, Stanford graduate student Shayan Gharan, și Aleksander Madry, acum de la École Polytechnique Fédérale de Lausanne, în Elveția, a arătat că noua rotunjire tehnica ar putea produce un bun algoritm de aproximare pentru o variație de problema comis-voiajorului, „asimetrice” caz. În anul următor, Saberi, Gharan și Mohit Singh de la Universitatea McGill a folosit aceeași abordare pentru a dezvolta un nou algoritm de aproximare pentru comun comis-voiajorului problema.,având în vedere o hartă a orașelor și autostrăzilor, noul algoritm începe prin calcularea soluției fracționale exacte a problemei vânzătorului călător. Apoi, completează acea soluție fracționată la un copac care se întinde, care sperăm că se va apropia de atingerea echilibrului căutat între lungime și conversia ușoară într-o călătorie dus-întors. În cele din urmă, algoritmul conectează acel copac care se întinde — mai degrabă decât cel mai scurt copac — în cadrul lui Christofides.

noul algoritm a fost „o idee pe care am putea să o descriem într-o oră sau două, dar dovedind că a funcționat efectiv a durat mai mult de un an”, a spus Saberi.,

După o lungă analiză, Stanford-McGill echipa a fost în cele din urmă capabil de a bate Christofides’ algoritm cu o marjă mică de „grafice” comis-voiajor probleme, o gamă largă de subclasă. În câteva luni, alte grupuri, energizat de la Stanford-McGill succesul echipei, utilizate alte tehnici de rotunjire pentru a produce algoritmi pentru grafică caz cu mai bine de aproximări; înregistrarea curentă se ridică la 40 la sută, o îmbunătățire substanțială față Christofides’ 50 la sută.,

grafic caz „încapsulează o mulțime de aceleași dificultăți pe care le întâmpină în general o problemă,” Arora a spus, adăugând că aceleași tehnici care lucrează pentru grafică caz poate fi adus să le suporte în general comis-voiajorului problema.cu toate acestea, Saberi a spus, rezolvarea problemei de aproximare a vânzătorului călător în generalitatea sa completă va necesita probabil o infuzie de idei noi.,

„descoperirea matematică este ca și cum ți-ai simți drumul într-o cameră întunecată: să-ți pui mâna aici și să găsești un scaun, să-ți pui mâna acolo și să găsești o masă”, a spus el, parafrazându-l pe matematicianul Andrew Wiles. „La un moment dat, mâna ta lovește comutatorul de lumină și brusc totul are sens. Pentru problema vânzătorului călător, chiar și după atâtea hârtii care au împins plicul în atâtea direcții, nu cred că am lovit încă acel comutator.”

original story retipărită cu permisiunea Simons Science News, o divizie editorial independent de SimonsFoundation.,org a cărui misiune este de a spori înțelegerea publică a științei prin acoperirea evoluțiilor și tendințelor de cercetare în matematică și Informatică, Fizică și științele vieții.