Giga Mundo - Computação

Olá! Agora que já introduzi um pouco sobre busca em largura em Inteligência Artificial (se não está lembrado, por favor, verifique o artigo Busca em árvores ou grafos), está na hora de vermos um pouco da prática deste assunto: que tal, então, resolver um sliding puzzle usando busca em largura?

O que é um sliding puzzle?

Obviamente, para resolvermos um problema primeiro precisamos conhecer o mesmo. O sliding puzzle é aquele jogo de quebra-cabeças com peças movíveis, todas geralmente quadradas e que o jogador deve deslizá-las a fim de criar uma determinada combinação das mesmas.

Nós falamos sobre ele no artigo que citamos anteriormente, então que tal trazermos aqui uma imagem do mesmo para ajudar-nos a lembrar?

Pronto, aqui está ele! O tabuleiro à direita é a configuração que queremos alcançar no jogo e o tabuleiro à esquerda é obtido a partir de algum embaralhamento das peças, sempre deslizando-as para ocupar o espaço vazio. Desta forma, o jogador possui inicialmente o tabuleiro embaralhado (à esquerda) e deve mover as peças até ele ser reorganizado, conforme mostra a imagem à direita.

Esse tipo de problema é solucionável pela busca em largura e, o que é melhor, ela retornará a primeira melhor solução (em número de movimentos).

Desenvolvendo a aplicação

A aplicação não é lá “coisa de outro mundo” para ser criada - eu, por exemplo, levei quase duas horas para desenvovê-la por completo e com sucesso (é, mas se levarmos em consideração o fato de que sou o professor da disciplina… XD ).

Tal aplicação utiliza-se basicamente de todos os conceitos envolvidos na busca em largura que, para quem não está lembrado quais são, tratam-se de:

• Saber manusear estruturas de dados como listas, pilhas e filas (quem estiver com dúvidas sobre isso, por favor, verifique o artigo com Material do Curso de Estrutura de Dados 1);
• Compreender corretamente como efetuar a busca em largura (verifique o artigo que citei no início deste);
• Saber empilhar corretamente os estados solução para mais tarde imprimir em tela.

Quem quiser baixar a implementação desta aplicação em Pascal, baixe o seguinte arquivo:

Sliding puzzle usando busca em largura em Pascal

Esse arquivo contém o arquivo *.pas e a aplicação em *.exe.

Estou disponibilizando aqui para que vocês possam estudar o algoritmo e entender como o mesmo funciona.

Considerações a partir dos testes

Após a implementação, executei alguns testes a partir de tabuleiros embaralhados 20, 30 e 100 vezes.

No caso de tabuleiros embaralhados vinte vezes, o tempo necessário para a solução não foi maior do que um ou dois segundos.

Já no caso de tabuleiros embaralhados trinta vezes, o tempo variou de 6 a 10 segundos, em média.

Como se pode imaginar, no caso de um tabuleiro embaralhado cem vezes, o tempo necessário foi bem maior. Na verdade, devido a restrições de alocação de memória do Pascal (lembrem-se que o Turbo Pascal funciona em modo DOS, não Win32), houve estouro de pilha em memória e a execução foi encerrada.

Isso se deve à quantidade de níveis que a aplicação teve que descer para alcançar a resposta - lembre-se que a busca em largura vai abrindo TODOS os nós do próximo nível enquanto não encontra a solução no nível atual!

A partir de um determinado estado do tabuleiro, podemos ir para quatro outros (”movendo o espaço” para cima, para baixo, para a esquerda ou para a direita), então do estado inicial temos quatro possíveis. A partir daí, evitando as repetições, poderemos ter no máximo três filhos para cada nó (lembre-se que um movimento retornará ao estado do nó-pai, então esse já está descartado).

Se encontrarmos a solução no primeiro nível, teremos aberto, no máximo, 5 nós (nó raiz + quatro nós filhos).

Se encontrarmos no segundo nível, teremos aberto, no máximo, 17 nós.

Se encontrarmos no terceiro nível, teremos aberto, no máximo, 53 nós.

Agora, faça as contas e me responda: quantos nós serão abertos, no máximo, se precisarmos ir até o vigésimo nível?

Bem, agora é com vocês - busquem outras aplicações que vocês possam resolver com busca em largura.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]