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

https://hrcak.srce.hr/307609

Datum izdavanja:

30.12.2022.

Posjeta: 117 *