Re: sokoban

[Fábio Dias Moreira <fabiodias@xxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Em Qua 18 Jul 2001 09:40, Paulo Santa Rita escreveu:

> [snip]
>
> DIAGRAMA DE UMA ESTRATEGIA
>
> Uma estrategia pode ser descrita assim ( vou imaginar duas caixas e um
> motor )
>
> [snip]
>
> Evidentemente que o problema ainda esta longe de ser resolvido, mas ja
> temos alguns instrumentos matematicos que podem descreve-los. Nao sei se
> sao os melhores, mas e um comeco. E entao, eu dei o passe : voce agora faz
> o gol ?

Vou adicionar aqui que, provavelmente, qualquer algoritmo que resolve um jogo 
de Sokoban não deve ser muito melhor que força bruta. O site [URL: 
http://web.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html] prova que é 
possível simular uma máquina de Turing com o jogo de Sokoban. Em particular, 
é possível implementar um problema NP-completo.

Como os problemas NP-completos levam tempo exponencial (pelo menos com os 
melhores algoritmos conhecidos), resolver um jogo de Sokoban também deve 
levar tempo exponencial (a não ser que vcs encontrem um algoritmo esperto o 
bastante, o que implica num algoritmo melhor para resolver problemas 
NP-completos). Em particular, se vcs encontrarem um algoritmo que rode em 
tempo polinomial, vcs podem se considerar donos de um milhão de dólares :) 
[URL: http://www.claymath.org/prizeproblems/statement.htm] [URL: 
http://www.claymath.org/prizeproblems/pvsnp.htm].

[]s,

- -----------------------------------------------------------------
         Fabio Dias (fabiodias@ieg.com.br, ICQ# 31136103)
          RPG em Revista: A sua revista virtual de RPG!
           ====> http://www.rpgemrevista.f2s.com/ <====
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE7Vl8mW7XDIUgHE2YRAnnXAKCK087B8hMu0zUjLTsF1w9iRlPUPgCfcOJC
Ff89JePcdJOOt4/UkghT9Is=
=STEH
-----END PGP SIGNATURE-----