Re: sokoban

["Ralph Costa Teixeira" <ralph@xxxxxxxxxxxxxx>]

    Oi, gente.

    Que seja dito que alguns algoritmos de força bruta ainda resolvem se o
espaço de estados não for imenso; mas quando o espaço cresce... :(. Eu estou
maravilhado com o site do Sethian

http://www.math.berkeley.edu/~sethian/

que tem uma classe de algoritmos chamados Fast Marching Methods que, por um
lado, não têm nada de mais, mas são rápidos porque "fazem a força bruta na
ordem certa". Para um exemplo, vejam o exemplo do robozinho na pista de
obstáculos

http://www.math.berkeley.edu/~sethian/Applets/java_robotics.html

    Essencialmente, o algoritmo analisa TODAS as posições do robozinho
possíveis no grid (um espaço tridimensional -- duas variáveis para as
coordenadas do centro de massa, uma para o ângulo de rotação) e determina se
são possíveis ou não, e quão longe cada uma delas está do estado inicial (o
truque é analisar os estados na ordem correta; para quem já viu programação
dinâmica, é quase a mesma coisa; aliás, para quem quer pensar nisso e não
viu programação dinâmica, procure aprender, não é muito difícil e é bem
bonitinho; infelizmente não me lembro do texto onde eu aprendi). Daí para
achar caminhos mínimos é um pulinho.

    O problema do Sokoban pode ser resolvido com um algoritmo força bruta
tipo programação dinâmica... O problema é que o número de estados possíveis
é MUITO mais alto do que nesse exemplo do robozinho. No robo, a coisa é do
tipo N^3 (digamos, NxN posições possíveis para o centro de massa, N
possibilidades de ângulos de rotação). No Sokoban, se o labirinto tem umas
M^2 casas e temos uns P objetos (mais o jogador), há então uns M^2.C(M^2,P)
possíveis estados do jogo, que tem uma cara de M^(2P)... Eu ainda apostaria
(se alguém souber melhor, confirme ou disminta) que um algoritmo tipo
programação dinâmica resolve os problemas do Sokoban QUE TÊM SOLUÇÃO que A
GENTE ENCONTRA no joguinho, mas deve se perder completamente nos
impossíveis...

    Abraço,
        Ralph