Znanstvenici uspostavili najbolji algoritam za kretanje zemljovidom

Da biste ovu proceduru primijenili u praksi, trebali biste se odlučiti za sustav za organiziranje svojih bilješki – strukturu podataka, u žargonu računalne znanosti. To može zvučati kao manji tehnički detalj, ali vrijeme potrošeno na pretraživanje vaših bilješki kad god trebate urediti ili ukloniti unos može imati veliki učinak na ukupno vrijeme rada algoritma.

Dijkstrin rad koristio je jednostavnu strukturu podataka koja je ostavila prostora za poboljšanje. U sljedećim desetljećima istraživači su razvili bolje, od milja nazvane “hrpe”, u kojima je neke predmete lakše pronaći od drugih. Oni iskorištavaju činjenicu da Dijkstrin algoritam treba samo ukloniti unos za najbliži preostali vrh. “Gomila je u osnovi struktura podataka koja vam omogućuje da to učinite vrlo brzo”, rekao je Vaclav Rozhon istraživač na Institutu za računalne znanosti, umjetnu inteligenciju i tehnologiju (INSAIT) u Sofiji, Bugarska.

Godine 1984. dva računalna znanstvenika razvila su a pametan dizajn hrpe to je omogućilo Dijkstrinom algoritmu da dosegne teoretsku granicu, ili “donju granicu,” vremena potrebnog za rješavanje problema najkraćih puteva s jednim izvorom. U jednom specifičnom smislu, ova verzija Dijkstrinog algoritma je najbolja moguća. To je bila posljednja riječ o standardnoj verziji problema gotovo 40 godina. Stvari su se promijenile tek kada je nekoliko istraživača pobliže promotrilo što znači biti “najbolji”.

Najbolje ponašanje

Istraživači obično uspoređuju algoritme proučavajući kako se ponašaju u najgorem slučaju. Zamislite najzbunjujuću uličnu mrežu na svijetu, a zatim dodajte neke posebno zbunjujuće prometne obrasce. Ako inzistirate na pronalaženju najbržih ruta u ovim ekstremnim okolnostima, verzija Dijkstrinog algoritma iz 1984. dokazano je nepobjediva.

No nadamo se da vaš grad nema najgoru uličnu mrežu na svijetu. Stoga se možete zapitati: postoji li algoritam koji je nepobjediv na svakoj cestovnoj mreži? Prvi korak u odgovoru na ovo pitanje je napraviti konzervativnu pretpostavku da svaka mreža ima najgore moguće obrasce prometa. Zatim želite da vaš algoritam pronađe najbrže staze kroz bilo koji mogući raspored grafikona, uz pretpostavku najgorih mogućih težina. Istraživači ovaj uvjet nazivaju “univerzalnom optimalnošću”. Kad biste imali univerzalno optimalan algoritam za jednostavniji problem jednostavnog prelaska s jedne točke na grafikonu na drugu, mogao bi vam pomoći da pobijedite prometnu gužvu u svakom gradu na svijetu.