|
|
 |
|
|
|
|
|
|
| Detalji |
| Projekt: |
Distribuirani algoritmi za pronalaženje optimalnih putova u grafovima |
| Voditelj: |
Robert Manger |
| Ustanova: |
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb |
| Sažetak: |
U operacijskim istraživanjima i računarstvu pojavljuje se porodica međusobno povezanih problema koji se svode na traženje optimalnih putova u grafovima. Neki od tih problema razmjerno su «lagani», dok preostali spadaju u klasu NP-teških. Primjeri laganih problema su: određivanje najkraćih, najduljih ili najpouzdanijih putova, pronalaženje maksimalnog toka u mreži, te off-line problem k poslužitelja. Primjeri NP-teških problema su: problem trgovačkog putnika, te problem usmjeravanja vozila. Distribuirani algoritmi su takvi postupci gdje više istovremenih procesa sudjeluje u rješavanju istog primjerka problema. Pritom ti procesi ne koriste zajedničke podatke ali razmjenjuju poruke. Cilj ovog projekta je: razviti nove distribuirane algoritme za odabrane probleme traženja optimalnih putova u grafovima. U pogledu odabira problema naglasak je na takozvanim obogaćenim varijantama NP-teškog problema usmjeravanja vozila, na on-line varijantama razmjerno laganih problema poput najkraćeg puta ili k poslužitelja, te na hibridima koji kombiniraju nekoliko klasičnih problema. U pogledu oblikovanja algoritama naglasak je na meta-heuristikama poput evolucijskog pristupa, na multipliciranim varijantama jednostavnih ali brzih heuristika poput pohlepnog pristupa ili lokalnog traženja, te na algebarskim metodama. Distribuirani rad će se realizirati kao rad većeg broja procesa na klasteru računala. Odabrani problemi su zanimljivi zato jer oni u odnosu na «akademske» probleme iz literature vjernije modeliraju stvarne životne situacije. Za te probleme potrebno je razvijati nove algoritme budući da algoritmi iz literature ne uzimaju u obzir njihova dodatna ograničenja ili kombinacije. Distribuirani algoritmi su potrebni zato što će zbog sve većih zahtjeva za računalnim resursima u potpuno umreženom svijetu budućnosti oni postati prevladavajući način rješavanja problema. Očekujemo da će projekt rezultirati većim brojem novih distribuiranih algoritama za pronalaženje optimalnih putova u grafovima. Za postizavanje i provjeru rezultata koristit ćemo matematičke izvode, metode softverskog inženjerstva uključujući i formalne metode, alate za paralelno programiranje, eksperimentiranje na klasterima računala, statističku obradu i vizualizaciju podataka. Važnost predloženog istraživanja je u stjecanju novih znanja, držanju koraka sa svjetskim tehnološkim razvojem, odgajanju znanstvenog podmlatka, te u mogućoj primjeni sofisticiranih znanja u hrvatskoj industriji. |
|
|
|
|
|
|
|
