ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrzej Novosiolov                   2:5020/400     06 Aug 2001  20:45:35
 To : Vadim Guchenko
 Subject : Re: Sokoban (логическая игра)
 -------------------------------------------------------------------------------- 
 

 On Mon, 06 Aug 2001 20:47:10 +0400, Vadim Guchenko wrote:
 
 > Существует ли алгоритм прохождения лабиринтов игры Sokoban?
 
 Если верить http://web.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html ,
 поиск решения для произвольного лабиринта Sokoban является PSPACE-полной (в
 другой формулировке - NP-трудной) задачей, что ещё хуже, чем NP-полная задача.
 К счастью, реальные лабиринты, как правило, не лишком страшны и вроде бы
 берутся за приемлемое время различными переборными алгоритмами.
 
 См. также:
 http://www.noether.freeserve.co.uk/soksolv/doc/
 http://www.cs.ualberta.ca/~games/Sokoban/program.html
 
 ... 2:463/1124.5@fidonet, ICQ 8481158, http://surf.to/andrzej
 --- ifmail v.2.15dev5
  * Origin: SoftElegance (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Sokoban (логическая игра)   Vadim Guchenko   06 Aug 2001 21:47:10   Re: Sokoban (логическая игра)   Andrzej Novosiolov   06 Aug 2001 20:45:35   Re: Sokoban (логическая игра)   Oleg Ponomarev   07 Aug 2001 10:48:45   Re: Sokoban (логическая игра)   Andrey Dashkovsky   06 Aug 2001 23:19:30   Sokoban (логическая игра)   Kostya Sudilovsky   11 Aug 2001 00:01:02   Re: Sokoban (логическая игра)   Andrey Dashkovsky   17 Aug 2001 16:25:33   Sokoban (логическая игра)   Serg Belyaev   08 Aug 2001 21:41:41   Sokoban (логическая игра)   Kostya Sudilovsky   11 Aug 2001 00:18:13   Sokoban (логическая игра)   Vadim Guchenko   13 Aug 2001 18:51:46