Naslov diplomskega dela: Hevristični algoritmi za iskanje poti v štirismernih grafih

Povzetek:

V diplomskem delu smo implementirali in primerjali štiri algoritme za iskanje poti na štirismerno povezanih mrežnih grafih: A*, ALT, HPA* in JPS4. Algoritme smo testirali na osmih zemljevidih velikosti 512×512 vozlišč — šestih iz igre Baldur’s Gate 2, labirintu in naključnem zemlje vidu z desetimi odstotki ovir. Za vsak algoritem smo merili čas predprocesiranja, čas iskanja poti, število raziskanih vozlišč in dolžino najdene poti. Algoritem JPS4 se je izkazal kot najboljši na večini metrik. Dosegel je povprečno 23,38-kratni pospešek v primerjavi z algoritmom A*, raziskal
79,54% manj vozlišč, pri tem pa ohranja optimalno dolžino poti. Ker ne potrebuje predprocesiranja, je primeren tako za statične kot dinamične grafe. Algoritem HPA* z regijami 8×8 je dosegel 15,22-kratni pospešek in nizko točko preloma, a je našel v povprečju za 1,52% daljšo pot. Algoritem ALT z 8 orientacijskimi točkami je prinesel 1,85-kratni pospešek. Odlikuje se na labirintskih strukturah, na odprtih zemljevidih pa je lahko bil celo počasnejši od A*.
Za večino praktičnih aplikacij je algoritem JPS4 najboljša izbira. Algo ritem HPA* postane konkurenčen pri velikem številu poizvedb na statičnih grafih, algoritem ALT pa je priporočljiv za iskanje poti v labirintskih okoljih.

Mentor: doc.dr.Luka Fürst

Komisija za zagovor:

    - izr.prof.dr. Tomaž Curk, Predsednik

    - doc.dr. Tomaž Dobravec, Član

    - doc.dr.Luka Fürst, Mentor

Prostor: Sejna soba 3