Djakstra

´ TRABALHO PRATICO 1: Labirinto
Marini Almeida Nascimento
1

Departamento de Matem´ tica e Ciencia da computacao a ¸˜ - Universidade Federal de Minas Gerais (UFMG) [e-mail] Resumo. Implementar um programa em linguagem C capaz de fazer um rato percorrer um labirinto e encontrar a sa´da. ı

1. INTRODUCAO ¸˜
´ O problema em estudo neste projeto e o problema de deslocamento no plano bidimensional, onde queremos determinar um caminho entre duas coordenadas. ` Este problema de deslocamento n˜ o e aplic´ vel somente a jogos. Podemos pensar a ´ a tamb´ m em um programa usado no GPS -sistema de posicionamento global- ,por exeme plo, para determinar o trajeto de um carro. Nesse trabalho ser´ determinado o caminho percorrido no plano em de certo rato a at´ encontrar a saida do labirinto. e

2. IMPLEMENTACAO ¸˜
Achar um caminho entre dois pontos quaisquer neste grafo basta testar todas as possibilidades. Entretanto, esta abordagem (conhecida como m´ todo de forca bruta) traz alguns e ¸ ´ bastante demorada e n˜ o garante que o caminho mais curto (ou com incovenientes: E a menor custo) seja encontrado. Por isso a ultilizacao de um algoritmo que ache o caminho mais curto seria con¸˜ veniente. Para podermos usar essa abordagem, decidimos interpretar o labirinto do projeto ´ como um grafo, onde cada caracter e um vertice do grafo e dois caracteres adjacentes diferentes de 1 formam uma aresta entre eles. Para a resolucao desse projeto foi usado o Algoritmo de Djkstra modificado para ¸˜ conseguir interpretar a estrutura de dados imposta pelo enunciado do trabalho como um grafo com essas caracteristicas. 2.1. Algoritmo de Djkstra modificado ´ O algoritmo de Dijkstra assemelha-se ao BFS, mas e um algoritmo guloso, ou seja, toma a ´ decis˜ o que parece otima no momento. Para a teoria dos grafos uma ”estrat´ gia gulosa”´ a e e conveniente j´ que sendo P um menor caminho entre 2 v´ rtices U e V, todo sub-caminho a e ´ de P e um menor caminho entre 2 v´ rtices