Proposta de trabalho – Métodos de busca para resolver um labirinto

A ideia desse trabalho é implementar algoritmos para resolver um labirinto. Métodos de busca em largura e busca em profundidade são os mais simples para experimentar, mas também pode ser implementado o algoritmo de busca A*.

É normal aprender sobre a busca em largura e profundidade em disciplina de estrutura de dados, onde e dada uma árvore e o algoritmo percorre a árvore até uma nó folha com o que se quer encontrar.

O trabalho aqui proposto visa aprender a usar efetivamente esses métodos de busca, onde não se tem uma árvore para ser percorrida, sendo necessário construir a árvore passo-a-passo, enquanto se “caminha” pelo labirinto.

É recomendado que a implementação leve em consideração os passos para formulação de um problema, que consistem em:

• Estado inicial: onde o agente começa;
• Ações (função sucessor): possíveis ações que o agente pode executar
• Resultado (modelo de transição): dado um estado e uma ação, especifica um novo estado
  • Result(S,a) = S’
• Teste de Objetivo: determina se o estado é objetivo ou não;
• Custo de Caminho: dado um caminho (sequencia de transições estado/ação) determina um número que é o custo daquele caminho
  • Na maioria dos problemas, a custo será aditivo, sendo assim, o custo de um caminho é a soma dos passos individuais
• Custo de Passo: a implementação do custo de caminho envolve o custo de passo. Este recebe um estado, uma ação e um resultado e retorna um número que é o custo da ação
  • StepCost(S,a,S’) = n

Existem diversos geradores de labirinto com código fonte disponível na internet e uma possibilidade é fazer uso desses geradores (o objetivo do trabalho e implementar os métodos de busca para solucionar o labirinto). Essas soluções já prontas de geração de labirinto são interessantes para aproveitar e estudar recursos de programação.

Para aqueles que preferem fazer algo mais simples, segue uma recomendação sobre o ambiente do labirinto: o método deve executar em um ambiente composto por uma matriz quadrada de ordem n (até 10) e nula. Células com valor 1 são por onde é possível se mover, células com valor 0 (zero) representarão lugares que o agente não poderá percorrer (paredes). A célula com valor 2 representa o local de onde o agente iniciará e a célula de valor 3 o lugar onde ele precisa chegar. Se as paredes forem adicionadas aleatoriamente, um cuidado que precisa ser tomado é que exista uma solução para o problema e isso não é fácil, por isso recomendo criar labirintos estáticos.

No caso de utilizar mapas estáticos, elabore alguns labirintos para avaliar. A figura abaixo ilustra um labirinto. Veja que existem várias formas de alcançar o objetivo. Coloquei também um caminho circular para dificultar (o algoritmo pode ficar preso no ciclo, dependendo da implementação).

Para implementação do método de busca, considere o custo de passo com valor igual para qualquer movimentação e que será permitida a movimentação em quadro direções (cima, baixo, esquerda e direita). A implementação deve ter uma função sucessor e uma função de teste de objetivo.

O vídeo a seguir é uma explicação de como aplicar a elaboração da árvore de busca para esse trabalho.