Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Copy of Trabalho de Inteligência Artificial Labirinto

Created by Rhuan Buarque
by

Dayane Passos

on 29 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of Trabalho de Inteligência Artificial Labirinto

Programação Buscas Cegas:
Busca em Largura:
Resolução de Labirintos utilizando
Inteligência Artificial
Arthur Gomes
Guilherme Nakayama
João Machado
Rhuan Buarque
Tipos de algoritmos:
Busca Cega;
Busca Heurística;
Busca Competitiva.
Neste trabalho trataremos das buscas cega e heurística.
A Busca Cega procura pelo nó objetivo sem utilizar nenhuma informação prévia
As Buscas Cegas usadas neste trabalho foram:
Busca em largura;
Busca em profundidade
Busca em Profundidade:
O usuário pode entrar com um valor para o menor tamanho de labirinto a ser executado, e em seguida será perguntado sobre o maior tamanho a ser executado, e então o usuário decide quantas vezes os algoritmos serão executados para cada tamanho.
Busca heurística:
Programação das Buscas Heurísticas:
Busca Gulosa;
Busca A*
Faz uso de uma fila.
Faz uso de uma pilha.
Busca heurística procura pelo nó objetivo utilizando alguma função de avaliação, no nosso caso a distância em linha reta entre o nó a ser expandido e o nó objetivo (fórmula de distância ponto a ponto).
A função heurística utilizada é conhecida como distância de ponto a ponto, dada pela fórmula:
Ambas usam listas, entretanto o algoritmo A* considera o caminho já percorrido.
Considerações finais:
A função heurística escolhida se mostrou consistente para o caso da busca gulosa, porém ao acrescentarmos o caminho percorrido ela pode ter prejudicado o resultado da busca A*.
O que pode ser constatado a partir dos resultados de tempo e de nós expandidos.
A busca em profundidade obteve um péssimo desempenho de memória alocada, pois ela pode procurar por caminhos que não levam a nada e então a memória alocada cresce muito.
Com a função de avaliação criada para dar uma "nota" aos resultados, percebemos que a busca gulosa, por ter uma função heurística que pode ser considerada boa, obteve um bom resultado.

Análise dos dados:
Para realizarmos uma análise dos dados foram feitas as medidas do tempo empíricamente, do número de nós expandidos e da maior quantidade de memória alocada.
Para melhor visualização foi feita uma média dos valores obtidos nos intervalos de tamanho dos labirintos.
Podemos observar que o algoritmo A* obteve o pior rendimento.
O algoritmo de Busca Gulosa obteve o melhor resultado
Nesse caso o algoritmo de profundidade obteve o pior resultado, como era esperado.
A busca gulosa obteve o melhor resultado levando em consideração todos os quesitos apresentados anteriormente.
Full transcript