Primerjava algoritmov iskanja poti in umetne inteligence v naključno generiranemu labirintu

Kaj je nastalo

Namen diplomskega dela je ugotovitev učinkovitosti in hitrosti različnih pristopov k reševanju poti v kompleksnih strukturah. V teoretičnem delu so obravnavani algoritmi iskanja najkrajše poti, in sicer algoritem A*, preiskovanje v širino in Dijkstrov algoritem. Predstavljena je tudi teorija grafov in mrež ter vloga hevristike pri iskanju poti.

Posebno poglavje je namenjeno umetni inteligenci in njenemu pomenu pri reševanju problema iskanja poti. Za empirično raziskavo je bila razvita aplikacija v programskem jeziku Python z grafičnim uporabniškim vmesnikom. Aplikacija omogoča generiranje naključnih labirintov različnih velikosti ter vizualizacijo delovanja posameznih algoritmov.

Za simulacijo umetne inteligence je bil implementiran pristop globokega Q-učenja z uporabo knjižnice PyTorch. Testiranje je potekalo na tisoč naključno generiranih labirintih za naslednje velikosti, in sicer 11×11, 21×21 in 31×31. Merjeni so bili čas iskanja, število obiskanih vozlišč in uspešno doseganje cilja.

Algoritmi iskanja poti so pokazali 100-% uspešnost pri vseh velikostih labirintov. Algoritem A* se je izkazal kot najbolj optimiziran z najmanjšim obiskom vozlišč, medtem ko je Dijkstrov algoritem najhitreje našel končno vozlišče. Umetna inteligenca je dosegla 60,3-% uspešnost na labirintih velikosti 11×11, vendar se je njena učinkovitost občutno zmanjšala pri večjih labirintih, in sicer 8,1-% uspešnost na labirintih velikosti 21×21 in 2,8-% uspešnost na labirintih velikosti 31×31.

Rezultati nakazujejo, da so tradicionalni algoritmi iskanja poti bolj zanesljivi in učinkoviti za praktične aplikacije, kjer je potrebna 100-% učinkovitost in uspešnost. Umetna inteligenca ponuja potencialno boljše rezultate, vendar zahteva obsežnejše učenje na raznolikih podatkih za doseganje primerljivih rezultatov z algoritmi iskanja poti. Diplomsko delo prispeva k boljšemu razumevanju prednosti in omejitev različnih pristopov iskanja poti v kompleksnih strukturah.

V prihodnosti bi bilo smiselno raziskati še druge metode umetne inteligence ter optimizirati procese učenja, da bi se dosegla večja uspešnost pri reševanju zahtevnejših labirintov.