Centar za edukaciju-BiH

Predmet:Svicarci razvili najbrzi mogući algoritam protoka mreze

---

Zahvaljujući ovom "algoritmu gotovo linearnog vremena" vrijeme racunanja i velicina mreze povećavaju se istom brzinom, kao da odrzavate isti tempo hoda koliko god put bio strm
Rasmus Kyng i njegov tim s ETH u Zürichu razvili su superbrzi algoritam mreznog protoka koji dostavlja rjesenje u trenutku kada racunalo cita podatke koji opisuju mrezu. Iako se istrazivaci ovim problemom bave već skoro cijelo stoljeće, sve dosad trebalo je znatno vise vremena za izracunavanje optimalnog protoka nego za obradu mreznih podataka. A kako je mreza postajala sve veća i slozenija, potrebno vrijeme racunanja raslo je puno brze od stvarne velicine racunalnog problema.
Optimalan protok
Zahvaljujući Kyngovom algoritmu, vrijeme racunanja i velicina mreze povećavaju se istom brzinom, kao da hodajući stalno odrzavate isti tempo koliko god put bio strm. Ove nove, gotovo optimalno brze algoritme znanstvenici su prozvali "algoritmima gotovo linearnog vremena".
Prvi algoritam, osmisljen prije dvije godine, bio je fokusiran na fiksne, staticne mreze usmjerenih veza koje funkcioniraju kao jednosmjerne ulice u mrezama gradskih cesta. Algoritmi objavljeni ove godine mogu izracunati i optimalne protoke za mreze koje se postupno mijenjaju tijekom vremena. Munjevito brzo racunanje vazan je korak u rjesavanju vrlo slozenih mreza bogatih podacima koje se mijenjaju dinamicki i vrlo brzo, poput molekula ili mozga u biologiji.
Munjevito brzi algoritmi za promjenu mreza
Novi algoritam s gotovo linearnim vremenom predstavljen je na godisnjem ACM simpoziju o teoriji racunalstva STOC u Vancouveru. Ovaj algoritam rjesava problem minimalne cijene i maksimalnog protoka za mreze koje se postupno mijenjaju kako se dodaju nove veze. A na jesen će svicarski istrazivaci na IEEE Simpoziju o temeljima racunalne znanosti FOCS predstaviti jos jedan algoritam koji upravlja uklanjanjem veza.
Ovi algoritmi identificiraju najkraće rute u mrezama gdje se veze dodaju ili brisu, bilo da je rijec o racunalu, online kartografskom servisu ili planeru rute. Oni, kazu, izracunavaju optimalnu rutu za ove inkrementalno ili dekrementalno promjenjive mreze u gotovo linearnom vremenu, i to tako brzo da je vrijeme racunanja za svaku novu vezu, bilo dodano preusmjeravanjem ili stvaranjem novih ruta, opet zanemarivo.
Najbolje od oba svijeta
Prije Kynga, informaticari su birali između dvije kljucne strategije. Jedna je modelirana na zeljeznickoj mrezi i ukljucuje racunanje cijelog dijela mreze s modificiranim protokom prometa u svakoj iteraciji. Druga, inspirirana tokovima u elektricnoj mrezi, izracunava cijelu mrezu u svakoj iteraciji, ali koristila statisticke srednje vrijednosti za modificirani tok svakog dijela mreze.
Svicarci su spojili prednosti ovih dviju strategija i stvorili radikalno novi, kombinirani pristup temeljen na brojim malim, ucinkovitim i jeftinim racunalnim koracima, koji su zajedno mnogo brzi od nekoliko velikih. Tome pridonosi i nova podatkovna struktura za organiziranje mreznih podataka koja vrlo brzo prepoznaje promjene mreznih veza.
Postavljanje temelja za rjesavanje vrlo velikih problema koji se prije nisu mogli ucinkovito izracunati samo je jedna od prednosti ovih znatno brzih algoritama; oni ujedno mijenjaju i nacin na koji racunala uopće izracunavaju slozene zadatke, kazu svicarski istrazivaci.

izvor: bug.hr

---