Legrövidebb út kereső algoritmusok hatékony megvalósítása

OData támogatás
Konzulens:
Dr. Horváth Gábor
Hálózati Rendszerek és Szolgáltatások Tanszék

A tudás megszerzése mellett a legfontosabb dolog a megszerzett tudás hasznosítása. A legrövidebb utak problémája régóta megtalálható történelmünkben. Az első térképészeti emlék nagyjából i. e. 6200 körülire tehető. Ekkor még a térképek csak tájékoztató vagy művészeti jelleggel bírtak. Később a gazdasági és társadalmi fejlődések hatására egyre igényesebb térképek készültek. Ezek segítségével már jól meg lehetett tervezni a katonai utánpótlások útvonalait vagy a kereskedelmi útvonalakat.

Az 1950-es évekre a számítógépek elterjedésével egyre több alkalmazás vált elérhetővé. A matematikában már régebben jelenlévő ábrázolási módok (pl. gráfok, halmazok) segítségével a legrövidebb utak keresése már számítógépen is elvégezhető volt. 1959-ben Edsger Wybe Dijkstra publikált egy a mai napig, kisebb változtatásokkal, használt igen hatékony útkereső algoritmust.

A közlekedés felgyorsulása, valamint a hálózati forgalom jobb kezelhetősége miatt (mind számítógépes, mind navigációs hálózatok esetében) egyre fontosabb lett a legrövidebb utak (nem feltétlen távolságban) gyors megtalálása. A GPS navigációs rendszereknél valamint a számítógépes hálózattervezésnél használt algoritmusok esetében a kritikus kérdés a sebesség.

Jelen szakdolgozatban a legrövidebb utak keresésének problémájára keresek hatékony megoldást. Főbb célhardver a CPU és a GPU. Ezeken a hardvereken implementált algoritmusok előnyeit és hátrányait fogom bemutatni.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.