Djakstra

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1055 palavras )
  • Download(s) : 0
  • Publicado : 10 de dezembro de 2012
Ler documento completo
Amostra do texto
´ TRABALHO PRATICO 1: Labirinto
Marini Almeida Nascimento
1

Departamento de Matem´ tica e Ciencia da computacao a ¸˜ - Universidade Federal de Minas Gerais (UFMG)
marinini.almeida@gmail.com

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 dedeslocamento 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 asaida 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 caminhomais 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 dotrabalho 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´ rticespertencentes ao caminho P, desta forma cone stru´mos os melhores caminhos dos v´ rtices alcancaveis pelo v´ rtice inicial determinando ı e ¸´ e todos os melhores caminhos intermedi´ rios. Nota: diz-se ’um menor caminho’ pois caso a existam 2 ’menores caminhos’ apenas um ser´ descoberto. a

COMPLEXIDADE classe: Algoritmo de busca estrutura de dados: Grafo complexidade pior caso: O(E+Vlog(V))sendo V = numero de vertices e E = numero de arestas; 1: carregaLabirinto
Labirinto* carregaLabirinto(char *nomeArquivo): Retorna um ponteiro para uma estrutura representando o labirinto especificado no arquivo [nomeArquivo]. a primeira linha do arquvo [nomeArquivo] deve conter dois inteiros especificando o numero C de colunas e L de linhas do labirinto. as proximas L linhas devem conter C caracteresrepresentando o labirinto. O(n ∗ m) n*m = linha * coluna

2: liberaLabirinto
void liberaLabirinto(Labirinto *lab): Libera toda a memoria utilizada por [lab] O(1)

3: inspeciona
char inspeciona(Labirinto *lab, Posicao *pos): Retorna o caractere na posicao [pos] do labirinto [lab] O(1)

4: coordenadaInicial
Posicao* coordenadaInicial(Labirinto *lab): cria e retorna a posicao da coordenadainicial (marcada com o caractere ’i’) no labirinto [lab]. O(n ∗ m) n*m = linha * coluna

5: criaPosicao
Posicao* criaPosicao(int x, int y): Cria uma estrutura representando a posicao [x, y]. O(1)

6: liberaPosicao
void liberaPosicao(Posicao *pos): Libera a memoria utilizada para representar a posicao [pos]. O(1)

7: achaSaida
Percurso* achaSaida(Labirinto *lab, Posicao *pos): Retorna umpercurso da posicao inicial [pos] ate a saida do labirinto [lab]. O(n log n)

8: imprimePercurso
void imprimePercurso(Percurso *perc, char *nomeArquivo): Imprime o percurso [perc] no arquivo [nomeArquivo] como definido na especificacao. O(n) n = tamanho do percurso

9: liberaPercurso
void liberaPercurso(Percurso *perc): Libera a memoria utilizada para representar o percurso [perc]. O(1)...
tracking img