Hevristični algoritmi za iskanje poti v štirismernih grafihČERNILEC, DOMEN (Avtor) Fürst, Luka (Mentor) Iskanje potianalizaJPSA*HPA*ALTV diplomskem delu smo implementirali in primerjali štiri algo ritme 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 predprocesi ranja, č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.20262026-03-23 08:19:59Diplomsko delo/naloga181017VisID: 38101COBISS_ID: 275574019sl