Ottucsák György (BME SZIT)
Adaptív
útvonal választás
Adott egy irányított körmentes
gráf, amelynek az élsúlyai (hibái)
tetszőleges (akár ellenséges) módon változhatnak. Ekkor az algoritmus
feladata, hogy
két kijelölt csomópont között időről-időre (körről-körre) válasszon
egy útvonalat úgy, hogy az
úton lévő élek élsúlyainak (hibáinak) összege minél kisebb legyen.
A többkarú bandita probléma esetén az algoritmus csak a választott
útvonal hibájáról kap információt. Erre a problémára olyan
algoritmusokat keresünk, amelyeknek átlagos kumulatív hibája n kör után a
legjobb utólag kiválasztott fix útvonal hibájától maximum
o(1)-gyel tér el és az élek számában is csak
polinomiális függése van. Az előadasban ilyen algoritmusokat
mutatunk be.
Irodalom:
http://www.jmlr.org/papers/
http://www.szit.bme.hu/~oti/
http://www.szit.bme.hu/~oti/
Időpont: dec. 2. kedd 16:15 Helye: BME, Z épület 2. em. 205.