Útvonaltervező algoritmusok teljesítményvizsgálata

OData támogatás
Konzulens:
Dr. Juhász Sándor
Automatizálási és Alkalmazott Informatikai Tanszék

A gráfokban történő útkeresésre több algoritmus is létezik. A szakdolgozatom célja, hogy ezeket térképen történő útvonaltervezésre alkalmazzam. Bemutatok egy nyíltan elérhető térképadatbázist, majd az irányított, súlyozott gráffá történő alakítását. Leírom, hogy az úthálózatban előforduló összetett alakzatok, mint például körforgalma, autópálya felhajtók hogy reprezentálhatóak gráffal. Részletesen jellemzek több keresési algoritmust. Ezek között szerepel kimerítő keresést alkalmazó, heurisztikus közelítéseket használó, valamint a gráf előzetes feldolgozásán alapuló módszer is.

A térkép adatainak tárolási módja nagymértékben meghatározza az algoritmusok hatékonyságát. Összehasonlítom a merevlemezen tárolt relációs adatbázis teljesítményét a memóriában tárolt összetett adatszerkezetekével.

A dolgozat első részében bemutatott algoritmusok futási jellemzőit Magyarország úthálózatán több véletlenszerűen választott pont közötti út megkeresésével tesztelem.

Végül kitekintésként bemutatok néhány párhuzamosítási lehetőséget.

Letölthető fájlok

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