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

iD8DBQE7VmRJW7XDIUgHE2YRAgsMAKCVdHh7zL6x3Sim9BDe3NfSoM77wgCdGrpq
3B/ekH7e1ltTA05a7Ma66nA=
=Yz4k
-----END PGP SIGNATURE-----