Gggg

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 dar suporte 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, State repetitions=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,