Iskanje in izvajanje paralelnih planov pri variantah igre 8 kvadratov

Janež, Jernej (avtor), Bratko, Ivan (mentor)

V tej nalogi smo si zadali problem iskanja pararelnih planov pri variantah igre 8 kvadratov. Uporabili smo algoritem A* in z uporabo različnih hevrističnih funkcij ugotovili, katere pripeljejo do boljše rešitve in katere do slabše. Primerjali smo štiri hevristične funkcije in glede na potrebe predlagali, katera je najbolj primerna za uporabo. Nekatere potrebujejo več časa in s tem pridejo do bolj kvalitetne rešitve, nekatere pa najdejo rešitev mnogo hitreje, a so zaradi tega rešitve slabše kvalitete.

• Jezik: Slovenski jezik
• Ključne besede: iskanje, pararelno izvajanje, A* algoritem, hevristične funkcije
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2017
• PID: 20.500.12556/RUL-94820
• Datum objave v RUL: 07.09.2017

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Finding and executing parallel plans for variants of the 8-puzzle problem

Izvleček

In this thesis we deal with the problem of finding parallel plans for variants of the 8-puzzle problem. We used the A* algorithm and experimented with different heuristic functions trying to guide the search. We compared four different heuristic functions and depending on the environment proposed the most suitable one. Some of them need more time to find a better solution and some are faster but may miss good quality solutions.

• Ključne besede: search, parallel execution, A* algorithm, heuristic functions