Gggg

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1364 palavras )
  • Download(s) : 0
  • Publicado : 14 de abril de 2013
Ler documento completo
Amostra do texto
Faculdade de Ciências e Tecnologia / Universidade Nova de Lisboa

Inteligência Artificial

TP1: Primeiro Trabalho Prático

Relatorio da Primeira Parte

Turno Prático.6 Docentes Carlos Viegas Damásio Susana Nascimento de Almeida Realizado por

Tiago Daniel nº32037 Tiago Pereira nº31691 Tiago Gonçalves nº32037

Introdução
Iniciou-se por implementar a classe GraphSearch, de forma a darsuporte aos algoritmos de BreadthFirst, UniformCost e DepthFirst. De seguida foi implementado o algoritmo A*. Para fins comparativos, apresentamos abaixo execuções do mesmo problema quer pelo A* quer pelo UniformCostSearch. Assim como uma pequena descrição da implementação do problema do Mars Rover, e por fim uma conclusão dos valores apresentados.

VacuumTest
BreadthFirstSearch: [LEFT, SUCK,RIGHT, SUCK, RIGHT, RIGHT, RIGHT, SUCK] {Node Expansions=5184, Nodes Generated=15553}

DepthFirstSearch: [LEFT, SUCK, RIGHT, RIGHT, RIGHT, RIGHT, SUCK, LEFT, LEFT, LEFT, SUCK] {Node Expansions=12, Nodes Generated=36, State repetitions=12, Runtime (s)=0.011595125}

UniformCostSearch: [LEFT, SUCK, RIGHT, SUCK, RIGHT, RIGHT, RIGHT, SUCK] {Node Expansions=29, Nodes Generated=88, Staterepetitions=48, Runtime (s)=0.017799259, Total Cost=8.0}

NPuzzle 3x3:
UniformCostSearch: [RIGHT, DOWN, LEFT, UP, LEFT, UP, RIGHT, RIGHT, DOWN, LEFT, LEFT, UP, RIGHT, RIGHT, DOWN, LEFT, DOWN, LEFT, UP, RIGHT, DOWN, RIGHT, UP, LEFT] {Node Expansions=141768, Nodes Generated=379535, State repetitions=180445, Runtime (s)=2.891445036, Total Cost=24.0}

AStar: [RIGHT, DOWN, LEFT, UP, LEFT, UP, RIGHT, RIGHT,DOWN, LEFT, LEFT, UP, RIGHT, RIGHT, DOWN, LEFT, DOWN, LEFT, UP, RIGHT, DOWN, RIGHT, UP, LEFT] {Node Expansions=442, Nodes Generated=1260, Runtime (s)=0.138339945, Total Cost=24.0}

NPuzzle 4x4:
UniformCostSearch: [Não chega ao fim, esgota os recursos]

AStar: [DOWN, LEFT, DOWN, LEFT, UP, RIGHT, DOWN, DOWN, RIGHT, RIGHT, UP, UP, UP, LEFT, LEFT, DOWN, DOWN, DOWN, RIGHT, UP, LEFT, LEFT, UP, UP,RIGHT, DOWN, DOWN, DOWN, RIGHT, RIGHT, UP, UP, UP, LEFT, LEFT, LEFT] {Node Expansions=108611, Nodes Generated=326255, Runtime (s)=24.562635132, Total Cost=36.0}

Os algoritmos BreadthFirstSearch e DepthFirstSearch por defenição não garantem a solução de melhor custo, e num problema desta dimensão, não foram sequer capazes de devolver um resultado para o problema. Sabe-se que, por definição, oUniformCostSearch nos dá o caminho com melhor custo. Porem num simples problema como este, podemos ver pelos dados acima que o Algoritmo de UniformCostSearch não foi capaz de devolver uma soluçao para o problema. No entanto o A*, que tem um desempenho muito superior ao do UniformCostSearch em nós expandidos ( o que se reflecte também no tempo de execução ), devolve o caminho de custo óptimo. Rover
{Node Expansions=829030, Nodes Generated=6621176, State repetitions=5778070, Runtime (s)=66.254023088, Total Cost=1202.5820789468569} [W, SW, SW, SW, SW, SW, W, W, W, W, W, W, SW, W, W, W, SW, W, W, W, SW, SW, W, W, W, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, W, SW, SW, W, SW, SW, SW, SW, SW, SW, W, W, SW, SW, SW, SW, W, W, W, W, SW, W, W, W, W, W,W, W, SW, SW, SW, SW, W, W, SW, W, W, W, W, SW, W, W, SW, SW, W, W, W, W, SW, SW, SW, W, W, SW, W, W, SW, W, W, SW, SW, W, SW, SW, SW, SW, SW, SW, SW, SW, SW, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, W, SW, W, W, W, W, W, W, W, SW, W, W, W, W, W, W, SW, W, W, SW, W, SW, W, W, SW, W, W, SW, W, W, SW, W, SW, W, W, SW, W, SW, W, W, SW, SW, W, W, SW, W, W, SW, SW, W, W, SW, SW, W,W, SW, SW, W, W, SW, SW, W, W, SW, SW, W, SW, W, SW, SW, W, W, SW, SW, W, SW, W, SW, SW, SW, W, SW, W, SW, W, SW, SW, W, SW, SW, SW, SW, SW, W, SW, SW, SW, W, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW, SW,...
tracking img