Slika 6.3 nam pove kumulativno porabljen ˇcas reˇsevanje testnih prime-rov; enostavneje povedano smo seˇstevali porabljen ˇcas vsakega posameznega primera. Na grafu je z modro barvo oznaˇcen naˇs algoritem in z rdeˇco JSoko.
Hitro je opazno, da je JSoko veliko boljˇsi. JSoko je za vse primere porabil malo manj kot eno uro, medtem ko je naˇs algoritem porabil pribliˇzno 8 ur in 20 minut. To testiranje lepo pokaˇze, da je bilo v algoritem JSoko vloˇzenega precej veˇc ˇcasa in znanja. Menimo, da bi se z implementacijo moˇznih iz-boljˇsav, ki so opisane v poglavju 5.5, naˇs algoritem moˇcno pribliˇzal drugim znanim algoritmom za reˇsevanje problema Sokoban.
Zanimivo je tudi, da naˇs algoritem ni naˇsel niti ene reˇsitve prej kot JSoko.
Slika 6.3: Kumulativna primerjava ˇcasa izvajanja obeh programov za vse primere (z modro naˇs program, z rdeˇco JSoko)
6.4 Prednosti in slabosti
Najveˇcja in najpomembnejˇsa razlika je hitrost izvajanja. Naˇs algoritem je precej poˇcasnejˇsi kot algoritem JSoko. Kljub temu pa ima naˇs algoritem eno prednost in ta je, da najde veˇc reˇsitev. To pomeni, ˇce v doloˇcenem ˇcasu
28 POGLAVJE 6. PRIMERJAVA ALGORITMOV
ne najde optimalne reˇsitve, je vseeno lahko naˇsel druge reˇsitve. JSoko, pri katerem se uporablja iskanje v ˇsirino, vedno najde le prvo, optimalno reˇsitev.
Lasten algoritem JSoko
+ v doloˇcenem ˇcasu lahko najde veˇc reˇsitev, ki niso nujno opti-malne
+ v neskonˇcnem ˇcasu bo vedno naˇsel reˇsitev
– poˇcasnejˇsi
+ hitrejˇsi
+ v neskonˇcnem ˇcasu bo vedno naˇsel reˇsitev
– najde le optimalno reˇsitev, kar lahko pomeni, da v doloˇcenem ˇcasu sploh ne najde reˇsitve
Tabela 6.1: Prednost in slabosti
Poglavje 7 Zakljuˇ cek
Glavni cilj diplomske naloge je bila analiza reˇsevanja problema Sokoban.
Za boljˇso analizo in pregled smo napisali tudi algoritem za reˇsevanje tega problema.
Izkazalo se je, da je reˇsevanje problema Sokoban zahtevnejˇse, kot izgleda na prvi pogled. Nekaj zaˇcetnih primerov je enostavnih, vendar se stvari hitro zapletejo. To je bilo lepo razvidno iz rezultatov testiranja, kjer smo primerjali naˇs algoritem s prosto dostopnim programom JSoko. Poleg tega smo z analizo NP-teˇzkih problemov in predvsem z analizo problema Sokoban dobili pregled nad teˇzavnostjo in kompleksnostjo teh problemov.
Ugotovitve
Praktiˇcni del diplomskega dela je bila predvsem implementacija algoritma.
Ker je najlaˇzje oceniti uˇcinkovitost algoritma s primerjavo z drugim algo-ritmom, smo naˇs algoritem testirali na 155 primerih in primerjali s prosto dostopnim algoritmom za reˇsevanje tega problema. Primerjali smo ˇcas pora-bljen za vsak posamezen primer in ˇcas porabljen za vse primere skupaj.
Izkazalo se je, da naˇs algoritem precej zaostaja, vendar so rezultati vseeno zadovoljivi, glede na to, da je bilo za algoritem JSoko porabljenega veliko veˇc dela.
29
30 POGLAVJE 7. ZAKLJU ˇCEK
Nadaljnje delo
Diplomsko delo sluˇzi kot nekakˇsen kratek uvod v reˇsevanje problema So-koban oziroma v reˇsevanje NP-teˇzkih problemov. V naslednjem koraku bi bilo potrebno izboljˇsati naˇs algoritem za reˇsevanje, ki se ne more primer-jati s trenutno vodilnimi algoritmi na podroˇcju reˇsevanja problema Sokoban.
Dodaten korak bi lahko bila tudi natanˇcnejˇsa raziskava podroˇcja NP-teˇzkih problemov. S tem bi lahko dodali tudi dokaz, da je Sokoban res NP-teˇzek problem.
Poglavje 8 Literatura
[1] Adi Botea, Martin M¨uller, and Jonathan Schaeffer. Computers and Ga-mes: Third International Conference, CG 2002, Edmonton, Canada, July 25–27, 2002. Revised Papers, chapter Using Abstraction for Plan-ning in Sokoban, pages 360–375. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.
[2] Joseph C. Culberson. Sokoban is PSPACE-complete. Technical Report TR 97-02, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada, 1997.
[3] Dorit Dor and Uri Zwick. Sokoban and other motion planning problems.
Computational Geometry, 13(4):215–228, 1999.
[4] Limor Drori and David Peleg. Faster exact solutions for some np-hard problems. Theoretical Computer Science, 287(2):473–499, 2002.
[5] Stefan Edelkamp. Planning with pattern databases. In Sixth European Conference on Planning, 2014.
[6] Michael R. Garey and David S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
31
32 POGLAVJE 8. LITERATURA
[7] Petr Jaruˇsek and Radek Pel´anek. Human problem solving: Sokoban case study. Technick´a zpr´ava, Fakulta informatiky, Masarykova univerzita, Brno, 2010.
[8] Andreas Junghanns, Andreas Junghanns, and Meinen Eltern. Pushing the limits: New developments in single-agent search. Technical report, 1999.
[9] Andreas Junghanns and Jonathan Schaeffer. Sokoban: Evaluating stan-dard single-agent search techniques in the presence of deadlock, pages 1–15. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998.
[10] Andreas Junghanns and Jonathan Schaeffer. Sokoban: Enhancing ge-neral single-agent search methods using domain knowledge. Artificial Intelligence, 129(1–2):219–251, 2001.
[11] Andreas Junghanns and Jonathan Schaeffer. Sokoban: improving the search with relevance cuts. Theoretical Computer Science, 252(1):151–
175, 2001.
[12] Natallia Kokash. An introduction to heuristic algorithms. Department of Informatics and Telecommunications, pages 1–8, 2005.
[13] Faculty of Science University of Alberta. Our program - rol-ling stone. https://webdocs.cs.ualberta.ca/~games/Sokoban/
program.html, 2016. [Dostopano, 7. 7. 2016].
[14] Andr´e G. Pereira, Marcus Ritt, and Luciana S. Buriol. Optimal so-koban solving using pattern databases with specific domain knowledge.
Artificial Intelligence, 227:52–70, 2015.
[15] Andr´e G Pereira, Robert Holte, Jonathan Schaeffer, Luciana S Buriol, and Marcus Ritt. Improved heuristic and tie-breaking for optimally solving sokoban.
33
[16] Timo Virkkala. Solving sokoban. Master’s thesis, University of Helsinki, Department of Computer Science, 4 2011.
[17] Sokoban Wiki. Deadlock.http://www.sokobano.de/wiki/index.php?
title=Deadlocks, 2016. [Dostopano, 28. 4. 2016].
[18] Sokoban Wiki. Solver statistics. http://sokobano.de/wiki/index.
php?title=Solver_Statistics, 2016. [Dostopano, 7. 7. 2016].
[19] Gerhard J. Woeginger. Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers, chapter Exact Algori-thms for NP-Hard Problems: A Survey, pages 185–207. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.
34 POGLAVJE 8. LITERATURA
Stvarno kazalo
A
A* 12
A* z iterativnim poglabljanjem 13
I
Iskanje v ˇsirino 10
Iskanje v globino 11
Iterativno poglabljanje 12
M
Manhattan distance 14
Mrtve toˇcke 21
N
NP problemi 3
NP-teˇzki problemi 3
O
Odloˇcitveni problemi 3
P
P problemi 3
Pravila prehodov med stanji 9
S
Single-agent search 9
Sokoban 5
T
Teorija raˇcunske zahtevnosti 6
35
36 STVARNO KAZALO
Dodatek A
Rezultati testiranja
37
38 DODATEK A. REZULTATI TESTIRANJA
Lasten algoritem JSoko algoritem primer ˇstevilo potez ˇcas (s) ˇstevilo potez ˇcas (s)
1 33 0.1 33 0.0
2 16 0.0 16 0.0
3 41 0.0 41 0.0
4 23 0.1 23 0.0
5 25 16.7 25 0.1
6 107 2.0 107 0.1
7 26 21.5 26 0.1
8 97 0.0 97 0.0
9 30 0.0 30 0.0
10 89 0.0 89 0.0
11 78 0.0 78 0.0
12 49 0.0 49 0.0
13 52 0.5 52 0.0
14 51 0.0 51 0.0
15 37 0.0 37 0.0
16 100 13.5 100 0.1
17 25 0.0 25 0.0
18 71 0.0 71 0.0
19 41 0.0 41 0.0
20 50 0.0 50 0.0
21 17 0.0 17 0.0
22 47 0.1 47 0.0
23 56 0.0 56 0.0
24 35 0.0 35 0.0
25 29 0.0 29 0.0
26 41 0.0 41 0.0
Tabela A.1: Rezultati 1/6
39
Lasten algoritem JSoko algoritem primer ˇstevilo potez ˇcas (s) ˇstevilo potez ˇcas (s)
27 50 0.0 50 0.0
28 33 0.0 33 0.0
29 104 0.1 104 0.0
30 21 0.0 21 0.0
31 17 0.0 17 0.0
32 35 0.0 35 0.0
33 41 0.2 41 0.0
34 30 1.3 30 0.0
35 77 83.6 77 0.3
36 0 600.0 156 0.6
37 71 0.4 71 0.0
38 37 0.0 37 0.0
39 85 0.1 85 0.0
40 20 0.0 20 0.0
41 50 0.0 50 0.0
42 47 0.1 47 0.0
43 61 0.3 61 0.0
44 1 0.0 1 0.0
45 45 0.0 45 0.0
46 47 0.0 47 0.0
47 83 0.1 83 0.0
48 64 0.3 64 0.0
49 82 0.3 82 0.0
50 76 0.1 76 0.0
51 34 0.0 34 0.0
52 26 0.3 26 0.0
Tabela A.2: Rezultati 2/6
40 DODATEK A. REZULTATI TESTIRANJA
Lasten algoritem JSoko algoritem primer ˇstevilo potez ˇcas (s) ˇstevilo potez ˇcas (s)
53 37 0.1 37 0.0
54 82 168.2 82 0.1
55 64 0.0 64 0.0
56 23 0.0 23 0.0
57 60 0.0 60 0.0
58 44 0.0 44 0.0
59 178 320.4 178 0.2
60 169 8.2 169 0.1
61 100 0.4 100 0.0
62 64 4.2 64 0.0
63 101 0.1 101 0.0
64 95 0.2 95 0.0
65 138 254.4 138 0.5
66 69 8.3 69 0.0
67 37 0.0 37 0.0
68 98 1.0 98 0.0
69 125 32.3 125 0.1
70 78 8.1 78 0.1
71 120 0.3 120 0.0
72 105 12.6 105 0.1
73 102 1.5 102 0.1
74 117 25.8 117 0.1
75 92 7.1 92 0.1
76 181 60.1 181 0.1
77 189 311.0 189 0.1
78 735 600.0 135 0.8
Tabela A.3: Rezultati 3/6
41
Lasten algoritem JSoko algoritem primer ˇstevilo potez ˇcas (s) ˇstevilo potez ˇcas (s)
79 48 0.0 48 0.0
80 131 51.4 131 0.0
81 46 0.1 46 0.0
82 52 0.0 52 0.0
83 868 600.0 164 0.2
84 201 454.8 201 0.2
85 155 446.5 155 0.1
86 105 8.6 105 0.0
87 781 600.0 149 0.2
88 195 319.8 195 0.1
89 222 600.0 146 0.2
90 64 38.9 64 0.1
91 45 0.1 45 0.0
92 126 48.0 126 0.0
93 0 600.0 0 600.0
94 83 1.0 83 0.0
95 104 600.0 25 0.2
96 92 16.8 92 0.0
97 514 600.0 164 0.2
98 0 600.0 269 2.8
99 0 600.0 349 15.8
100 155 44.8 155 0.0
101 79 40.8 79 0.1
102 669 600.0 149 0.1
103 35 0.6 35 0.0
104 79 4.3 79 0.0
Tabela A.4: Rezultati 4/6
42 DODATEK A. REZULTATI TESTIRANJA
Lasten algoritem JSoko algoritem primer ˇstevilo potez ˇcas (s) ˇstevilo potez ˇcas (s)
105 0 600.0 75 5.2
106 0 600.0 205 0.4
107 38 449.2 38 0.0
108 0 600.0 238 4.3
109 0 600.0 177 1.5
110 51 1.3 51 0.0
111 0 600.0 166 49.9
112 0 600.0 261 14.4
113 0 600.0 162 4.7
114 0 600.0 227 1.1
115 484 600.0 110 1.0
116 63 21.6 63 0.1
117 0 600.0 178 31.0
118 838 600.0 172 0.6
119 131 2.2 131 0.0
120 183 127.2 183 0.1
121 921 600.0 125 0.1
122 0 600.0 245 4.4
123 0 600.0 296 31.0
124 245 105.2 245 0.0
125 125 333.3 125 0.2
126 0 600.0 87 4.5
127 106 17.9 106 0.0
128 88 18.7 88 0.0
129 99 113.8 99 0.1
130 102 253.3 102 0.3
Tabela A.5: Rezultati 5/6