Rasmus Kyng i njegov tim s ETH u Zürichu razvili su superbrzi algoritam mrežnog protoka koji dostavlja rješenje u trenutku kada računalo čita podatke koji opisuju mrežu. Iako se istraživači ovim problemom bave već skoro cijelo stoljeće, sve dosad trebalo je znatno više vremena za izračunavanje optimalnog protoka nego za obradu mrežnih podataka. A kako je mreža postajala sve veća i složenija, potrebno vrijeme računanja raslo je puno brže od stvarne veličine računalnog problema. 

Optimalan protok

Zahvaljujući Kyngovom algoritmu, vrijeme računanja i veličina mreže povećavaju se istom brzinom, kao da hodajući stalno održavate isti tempo koliko god put bio strm. Ove nove, gotovo optimalno brze algoritme znanstvenici su prozvali "algoritmima gotovo linearnog vremena".

Prvi algoritam, osmišljen prije dvije godine, bio je fokusiran na fiksne, statične mreže usmjerenih veza koje funkcioniraju kao jednosmjerne ulice u mrežama gradskih cesta. Algoritmi objavljeni ove godine mogu izračunati i optimalne protoke za mreže koje se postupno mijenjaju tijekom vremena. Munjevito brzo računanje važan je korak u rješavanju vrlo složenih mreža bogatih podacima koje se mijenjaju dinamički i vrlo brzo, poput molekula ili mozga u biologiji.

Munjevito brzi algoritmi za promjenu mreža

Novi algoritam s gotovo linearnim vremenom predstavljen je na godišnjem ACM simpoziju o teoriji računalstva STOC u Vancouveru. Ovaj algoritam rješava problem minimalne cijene i maksimalnog protoka za mreže koje se postupno mijenjaju kako se dodaju nove veze. A na jesen će švicarski istraživači na IEEE Simpoziju o temeljima računalne znanosti FOCS predstaviti još jedan algoritam koji upravlja uklanjanjem veza.

Ovi algoritmi identificiraju najkraće rute u mrežama gdje se veze dodaju ili brišu, bilo da je riječ o računalu, online kartografskom servisu ili planeru rute. Oni, kažu, izračunavaju optimalnu rutu za ove inkrementalno ili dekrementalno promjenjive mreže u gotovo linearnom vremenu, i to tako brzo da je vrijeme računanja za svaku novu vezu, bilo dodano preusmjeravanjem ili stvaranjem novih ruta, opet zanemarivo.

Najbolje od oba svijeta

Prije Kynga, informatičari su birali između dvije ključne strategije. Jedna je modelirana na željezničkoj mreži i uključuje računanje cijelog dijela mreže s modificiranim protokom prometa u svakoj iteraciji. Druga, inspirirana tokovima u električnoj mreži, izračunava cijelu mrežu u svakoj iteraciji, ali koristila statističke srednje vrijednosti za modificirani tok svakog dijela mreže.

Švicarci su spojili prednosti ovih dviju strategija i stvorili radikalno novi, kombinirani pristup temeljen na brojim malim, učinkovitim i jeftinim računalnim koracima, koji su zajedno mnogo brži od nekoliko velikih. Tome pridonosi i nova podatkovna struktura za organiziranje mrežnih podataka koja vrlo brzo prepoznaje promjene mrežnih veza.

Postavljanje temelja za rješavanje vrlo velikih problema koji se prije nisu mogli učinkovito izračunati samo je jedna od prednosti ovih znatno bržih algoritama; oni ujedno mijenjaju i način na koji računala uopće izračunavaju složene zadatke, kažu švicarski istraživači.