Atividade Três Inteligência Artificial

Prévia do material em texto

UNIVERSIDADE VIRTUAL DO ESTADO DE SÃO PAULO 
 
 
 
 
 
PAULO CESAR NEVES - 1402082 
 
 
 
 
 
 
 
Engenharia da Computação – 18º bimestre 
Inteligência Artificial – Atividade Semana Três 
 
 
 
 
 
 
 
 
 
 
 
Polo Cidade Dutra 
 2018 
 
1 
UNIVERSIDADE VIRTUAL DO ESTADO DE SÃO PAULO 
 
 
 
 
 
 
 
 
Engenharia da Computação – 18º bimestre 
Inteligência Artificial – Atividade semana Três 
 
 
 
 
 
 
 
 
Atividade apresentada na semana três da 
disciplina de Inteligência Artificial (18º bimestre) 
para o curso de Engenharia de Computação da 
Fundação Universidade Virtual do Estado de São 
Paulo (UNIVESP). 
 
 
 
 
 
 
Polo Cidade Dutra 
 2018 
 
2 
 
Nome. Atividade da semana 3 – Inteligência Artificial. 00f. Relatório Técnico-
Científico (Engenharia de Computação) – Universidade Virtual do Estado de São 
Paulo. Polo, 2018. 
 
 
RESUMO 
 
Este trabalho apresenta os 5 exercícios solicitados como atividade referente à terceira 
semana da disciplina “Inteligência Artificial” do 18º bimestre do curso de Engenharia da 
Computação da Universidade Virtual do Estado de São Paulo (UNIVESP). Os 
exercícios tratam de diferentes tipos de busca (largura, profundidade, gulosa e A*) para 
descrever o caminho do estado inicial S ao estado objetivo G a partir de heurística 
dada. 
 
PALAVRAS-CHAVE: Inteligência Artificial; tipos de busca; heurística. 
 
 
3 
 
 
ABSTRACT 
 
This work presents the 5 exercises requested as an activity related to the third week of 
the discipline "Artificial Intelligence" of the 18th bimester of the Computer Engineering 
course of the Virtual University of the State of São Paulo (UNIVESP). The exercises 
deal with different types of search (width, depth, greedy and A *) to describe the path 
from the initial state S to the target state G from given heuristics. 
 
KEY WORDS: Artificial Intelligence; types of search; heuristic. 
 
 
 
 
4 
SUMÁRIO 
 
RESUMO ...................................................................................................................... 2 
ABSTRACT................................................................................................................... 3 
1. INTRODUÇÃO.......................................................................................................... 5 
2. EXERCÍCIO 1 ........................................................................................................... 6 
3. EXERCÍCIO 2 ........................................................................................................... 7 
4. EXERCÍCIO 3 ........................................................................................................... 8 
5. EXERCÍCIO 4 ........................................................................................................... 9 
6. EXERCÍCIO 5 ......................................................................................................... 10 
 
 
 
5 
1. INTRODUÇÃO 
 
Considere o seguinte grafo de estados, em que as arestas são rotuladas com o 
custo da ação correspondente: 
Figura 1 – Grafo de Estados. 
 
 
Para cada estratégia de busca a seguir, descreva o caminho que será 
encontrado do estado inicial S ao estado objetivo G. Considere a seguinte heurística: 
h(S) = 5, h(A)=3, h(B)=2, h(C)=4, h(D)=4, h(E)=1, h(F)=2 e h(G)=0. Caso haja empate, 
eles devem ser expandidos em ordem alfabética. 
 
 
6 
2. EXERCÍCIO 1 
 
Busca em largura: {S, A, E, G} 
 
Figura 2 – Busca em largura. 
 
 
 
7 
3. EXERCÍCIO 2 
 
Busca em profundidade: {S, A, E, D, F, G} 
 
Figura 3 – Busca em profundidade. 
 
 
8 
4. EXERCÍCIO 3 
 
Busca gulosa: {S, B, E, G} 
 
Figura 4 – Busca gulosa. 
 
 
9 
5. EXERCÍCIO 4 
 
Busca A*: {S, A, E, G} 
 
Figura 5 – Busca A*. 
 
 
10 
6. EXERCÍCIO 5 
 
Se o nó objetivo fosse o D, a heurística h(S)=3, h(A)=2, h(B)=2, h(C)=1, h(D)=0, h(E)=1, 
h(F)=5 e h(G)=5 seria admissível? Por que? 
Sim, porque em nenhum momento, entre S e D, o custo real seria superado pelo custo 
estimado.