Stručni rad
Sokoban je NP --težak
Stjepan Požgaj
; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet
Mladen Vuković
; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet
Sažetak
Kod raznih igara često je važno pitanje određivanja pobjedničke strategije. No, vrlo često se razmatraju i problemi računarske složenosti u vezi igara (vidi [2]). U ovom članku se razmatra računarska složenost povezana s igrom Sokoban.
Sokoban je poznata stara računalna igra u kojoj igrač (skladištar) mora odgurati sve kutije u skladištu na odgovarajuće pozicije, s tim da odjednom smije gurati najviše jednu kutiju. Osnovnu verziju igre možete isprobati na sljedećoj poveznici: https://sokoban.info/.
U ovom članku dat ćemo dokaze NP-težine dviju varijanti igre Sokoban.
Ključne riječi
kompjuterske igre; složenost algoritama; sokoban; teorija igara; tetris
Hrčak ID:
307609
URI
Datum izdavanja:
30.12.2022.
Posjeta: 389 *