Iskanje in izvajanje paralelnih planov pri variantah igre 8 kvadratov

Janež, Jernej (author), 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.

• Language: Slovenian
• Keywords: iskanje, pararelno izvajanje, A* algoritem, hevristične funkcije
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-94820
• Publication date in RUL: 07.09.2017

Secondary language

• Language: English
• Title: Finding and executing parallel plans for variants of the 8-puzzle problem

Abstract

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.

• Keywords: search, parallel execution, A* algorithm, heuristic functions