Novi algoritam brže pronalazi najkraće staze

Izvorna verzija od ova priča pojavio se u Magazin Quanta.

Ako želite riješiti škakljiv problem, to često pomaže da se organizirate. Možda ćete, na primjer, razbiti problem na komade i prvo riješiti najlakše komade. Ali ova vrsta sortiranja ima troškove. Možda ćete na kraju potrošiti previše vremena da redom uređuju komade.

Ova je dilema posebno relevantna za jedan od najslavnijih problema u informatici: pronalaženje najkraćeg puta od određenog polazišta u mreži do svake druge točke. To je poput sukopljene verzije problema koji morate riješiti svaki put kada se krećete: učenje najboljeg rute od svog novog doma do posla, teretane i supermarketa.

“Najkraće staze lijep je problem s kojim se svatko na svijetu može povezati”, rekao je Mikkel Thorupračunalni znanstvenik sa Sveučilišta u Kopenhagenu.

Intuitivno, trebalo bi biti najlakše pronaći najkraći put do obližnjih odredišta. Dakle, ako želite dizajnirati najbrži mogući algoritam za problem s najkraćim stazama, čini se razumnim započeti pronalaženjem najbliže točke, zatim sljedećeg okruženja i tako dalje. Ali da biste to učinili, morate više puta shvatiti koja je točka najbliža. Točke ćete sortirati prema udaljenosti dok idete. Postoji temeljno ograničenje brzine za bilo koji algoritam koji slijedi ovaj pristup: ne možete ići brže od vremena koje je potrebno za sortiranje.

Prije četrdeset godina istraživači koji su dizajnirali algoritme najkraćih staza protiv ove “barijere za razvrstavanje”. Sada je tim istraživača osmislio Novi algoritam koji ga razbija. To se ne sortira, a teče brže od bilo kojeg algoritma koji to čini.

“Autori su bili hrabri misleći da mogu razbiti ovu barijeru”, rekao je Robert Tarjanračunalni znanstvenik na Sveučilištu Princeton. “To je nevjerojatan rezultat.”

Granica znanja

Da bi matematički analizirali problem s najkraćim stazama, istraživači koriste jezik grafova-mreže točaka ili čvorova, povezani linije. Svaka veza između čvorova označena je s brojem koja se naziva njegova težina, što može predstavljati duljinu tog segmenta ili vremena potrebnog za prelazak. Obično postoji mnogo ruta između bilo kojih dva čvora, a najkraće je one čije utege dodaju najmanji broj. S obzirom na grafikon i određeni “izvorni” čvor, cilj algoritma je pronaći najkraći put do svakog drugog čvora.

A Najpoznatiji algoritam najkraće staze,, osmišljen Prema pionirskom računalnom znanstveniku Edsger Dijkstra 1956. godine, započinje s izvorom i radi prema van. To je učinkovit pristup, jer vam poznavanje najkraće staze do obližnjih čvorova može vam pomoći da pronađete najkraće staze do udaljenijih. No, budući da je krajnji rezultat sortirani popis najkraćih staza, barijera za sortiranje postavlja temeljno ograničenje koliko brzo algoritam može pokrenuti.