Ola Pessoal,
Para efeitos de contraditorio e para que o colega Niski, que propos a
questao, nao se sinta desistimulado em sua louvavel pretensao de formalizar
o jogo de sokoban, e importante que se registre que o interesse em encontrar
um algoritmo para o jogo nao esta, a principio, preocupado com aspectos
operacionais ...
Para a Tecnologia e a para a Pratica as questoes de tempo, eficiencia e
eficacia sao fundamentais e irremediaveis, isto e, em qualquer projeto e
fundamental provar que ele, alem de bom e correto, seja tambem viavel nas
dimensoes do tempo ( vamos gastar um tempo bem finito para realiza-lo ? )
e das financas ( Ha dinheiro suficiente pra realiza-lo ? )
Nao me parece que estes aspectos operacionais sejam relevantes em um estudo
teorico. Sao, sim, nesta dimensao pura e teorica, aspectos de somenos
importancia ... Hoje nos sabemos, pela teoria Teoria da Relatividade Geral,
que podemos causar efeitos temporais sensacionais, tais como aqueles
expressos no paradoxo do gemeos. Nao ha ainda tecnologia para implementa-los
: significa que devemos abandonar tais estudos simplesmente porque eles sao
, atualmente, operacionalmente irrealizaveis ? Evidentemente que nao ! E o
imaginario dos homens que cria a praxis do futuro, assim dizia Gaston
Bachelar !
Se o algoritmo do jogo sokoban que viermos a achar seja de natureza
exponencial ( cresce muito rapido ) ou polinomial ( cresce mais lentamente )
e irrelevante, na dimensao de discussao teorica em que nos encontramos. E
inclusive irrelevante se vamos ou nao achar um algoritmo ... O investimento
da inteligencia em investigar e por si so compensador e louvavel,
independente dos resultados praticos que dai promanem !
Por outro lado, e evidentemente falso e TALVEZ uma demonstracao de pura
prepotencia avaliarmos que qualquer outra(s) mente(s) diferente da nossa nao
possa encontrar algo melhor do que aquilo que conseguimos fazer e que ja
conhecemos : Se aquilo que eu conheco e consigo fazer e so forca bruta DEVO
CONCLUIR que MUITO PROVAVELMENTE alguma outra inteligencia podera e devera
encontrar algo melhor que isso ... Nao o contrario : Pois e isso que a
historia da ciencia vem demonstrando acontecer ao longo dos seculos !
Considere o seguinte problema :
Existe um algoritmo que recebe uma equacao diofantina generica e devolve
sim, caso ela tenha uma solucao no anel dos inteiros, ou nao, no caso
contrario ?
Um Matematico Russo provou que nao existe um tal algoritmo. Significa,
portanto, que jamais existira um programa de computador que implemente este
algoritmo, em tempo polinomial ou nao, qualquer que seja a linguagem.
Nao devemos, portanto, nunca mais estudar quaisquer equacoes diofantinas
... Ah, eu ia esquecendo ... Nem toda Matematica cabe no copinho da teoria
de computacao ...
Um abraco
Paulo Santa Rita
5,1337,19072001
From: Fábio Dias Moreira [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: sokoban
Date: Thu, 19 Jul 2001 01:38:23 -0300
-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 ([EMAIL PROTECTED], 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-
_
Seja avisado de novas mensagens do
