20.500.12556/RUL-84958 Reševanje problema Sokoban Solving the Sokoban problem Sokoban je igra s preprostimi pravili, vendar pa je reševanje kar velik zalogaj tako za človeka kot tudi računalnik. Ta problem je NP-težek, kar pomeni, da zanj domnevno ne obstaja polinomsko časovno omejen algoritem. Da najdemo optimalno rešitev, moramo pregledati vsa stanja. Zato se za reševanje uporabljajo iskalni algoritmi. Če želimo najti rešitev v krajšem času, moramo poiskati in implementirati kakovostno hevristiko. Vendar pa tudi trenutno najboljši programi za reševanje tega problema še dandanes niso sposobni najti rešitve za vse primere; to ne čudi, saj je problem NP-težek. Teoretični del te diplomske naloge je analiza problema Sokoban in NP-težkih problemov. Praktični del pa implementacija lastnega algoritma, ki smo ga primerjali z znanim algoritmom JSoko. Sokoban is a game with simple rules, but finding solutions is a hard task for both people and computers. Sokoban is a NP-hard problem, which means that we probably cannot find every optimal solution in polynomial time. Instead, we must check all possible states in order to find the optimal solution. Thus, search algorithms are used for solving Sokoban. If we want to find a solution in a reasonable time, we need to find and implement good heuristics. Of course, because Sokoban is NP-hard, even the best current algorithms cannot find solutions to all Sokoban puzzles. The theoritical part of the thesis is analysis of the Sokoban problem and NP-hard problems. Practical part consists of description of our algorithm. We also tested our algorithm and compared it to a well-known algorithm JSoko. Sokoban reševanje Sokobana NP-težki problemi iskalni algoritmi Sokoban solving Sokoban NP-hard problems search algorithms true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2016-09-08 16:00:01 2016-09-08 16:00:01 2022-08-02 06:42:46 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 18394 Klancar_Jaka_-_Resevanje_problema_Sokoban.pdf Klancar_Jaka_-_Resevanje_problema_Sokoban.pdf 1 0AE6C7CB2E7045FE474E705FB8B51729 0cffbbc93dc8ad65480e6759c1ad3a730b6c817d73880a31e4dcdf5bb466572f f12f3cd6-a1b0-11eb-a523-00155dcfd717 20.500.12556/rul/ead399bd-2521-4f2a-ae2b-8593e7e1ea01 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=88076 Fakulteta za računalništvo in informatiko 0 0 0