Simonyi Konferencia 2012 - Athén–Dublin: 12 másodperc

Készítették

Nem, nem, egy autó persze még nem lehet ilyen gyors. Egy algoritmus viszont már igen! A milliós nagyságrendű csúcsból és élből álló Európa térképén a klasszikus útkereső algoritmusok megfelelően működnek, ha eltekintünk a hosszú futási időtől és a tekintélyes memóriaigénytől, amelyek bizony jelentős korlátok hordozható eszközök esetében. Most viszont megtudhatod, mi az iGO titka, milyen algoritmus működik a felszín alatt, amely könnyedén győzi le a jó öreg Dijkstrát.

Napjaink digitális térképekkel lefedett úthálózata sokmillió útszakaszt, kereszteződést, elágazást foglal magába. A hatékony, gyors és közel optimális útvonalkeresés ekkora méretű gráfokon a hagyományos algoritmusok számára komoly kihívást jelent, figyelembe véve a navigációs eszközök korlátozott tárolási és számítási kapacitását. Az ésszerű gyorsítási lehetőségek, heurisztikák alkalmazása mellett ezért szükséges olyan új algoritmusok felkutatása is, amelyek matematikailag igazoltan lehetővé teszik, hogy gyorsan megtaláljuk a legjobb utat két pont között, akár teljes Európa úthálózatában, csupán pár másodperc alatt. Hanák Dávid előadásában egy ilyen algoritmust mutat be, amelynek hatékonyságát bizonyítja, hogy az NNG Kft. évek óta sikerrel alkalmazza navigációs termékeiben.

http://konferencia.simonyi.bme.hu

Letöltés

Normál minőség
Az esemény dátuma: 2012. április 17. kedd