Seminar za teorijsko računarstvo
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
12. veljače 2018. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo i njezini
studenti Luka Naglić, Domagoj Ravlić, Ante Sosa održat će predavanje pod
naslovom:
"Genetski algoritam za rješavanje problema metričkog k-centra".
Sažetak: Promatra se problem metričkog k-centra (Metric k-Center Problem).
Za dani neusmjereni, potpuni, euklidski graf G=(V,E) te za dani prirodni
broj k, treba pronaći k-člani podskup S skupa vrhova V tako da je maksimalna
udaljenost vrhova iz V\S do najbližeg vrha iz S minimalna. Riječ je o
NP-teškom problemu. Problem se rješava genetskim algoritmom čija je početna
populacija inicijalizirana algoritmom simuliranog kaljenja. Rezultati se
uspoređuju s rezultatima dobivenim trenutno najpoznatijim nepolinomijalnim
algoritmima za rješavanje problema k-centra na 40 standardnih grafova iz
"OR-Library".
Pozivaju se svi članovi Seminara kao i ostali zainteresirani da prisustvuju
ovom predavanju.
Robert Manger.