Aula 2 - IA - UNIVESP

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL 
 
Resolução de Problemas 
através de Busca 
 PROBLEMA 
Estado Inicial 
Ações 
Teste de Objetivo 
Custo 
 
PROBLEMAS 
Solução: sequência de ações que levam 
de um estado inicial a um objetivo. 
 
Solução ótima: solução de custo mínimo 
 ESPAÇO DE ESTADOS 
O conjunto de todos os estados 
acessíveis a partir de um estado 
inicial é chamado de espaço de 
estados. 
 
 ESPAÇO DE ESTADOS 
O espaço de estados pode ser 
interpretado como um grafo em que 
os nós são estados e os arcos são 
ações. 
 ESPAÇO DE ESTADOS 
Abstração do mundo real. 
 
Exemplo: Caminho de casa até o 
trabalho. Estados dados pela posição 
exata ou discretizados? 
 EXEMPLO (Aspirador de Pó) 
 EXEMPLO (Aspirador de Pó) 
• Estados: Posição do robô e sujeira (8) 
• Estado inicial: Qualquer um 
• Ações: esquerda (L), direita (R), 
aspirar(S) 
• Teste de objetivo: todas as posições 
estão limpas? 
• Custo do caminho: 1 cada passo 
 EXEMPLO (8 rainhas) 
 EXEMPLO (8 rainhas) 
• Estados: Qualquer disposição de 0 a 8 
rainhas 
• Estado inicial: Nenhuma rainha 
• Ações: colocar mais uma rainha 
• Teste de objetivo: 8 rainhas, 0 ataques 
 
64x63x...57 = 3x1014 possibilidades! 
 EXEMPLO (8 rainhas) 
• Estados: n rainhas nas n primeiras 
colunas, sem ataque 
• Ações: colocar uma rainha na próxima 
coluna, sem ataque. 
 
2.057 estados possíveis 
 
 BUSCA EM ÁRVORE 
Fronteira: nós a serem expandidos 
(começa com o estado inicial) 
 
A função Expande cria novos nós, 
usando as ações aplicáveis para gerar 
os estados correspondentes. 
 
 
 
 
 
 BUSCA EM ÁRVORE 
1. Retira o primeiro nó da fronteira (falha 
se vazia) 
2. Testa se é um estado final (solução): 
se for, devolve nó, sucesso 
3. Expande nó; 
4. Insere os nós gerados na fronteira e 
volta para o passo 1 
 
 ESTRATÉGIAS DE BUSCA 
A estratégia usada define a ordem 
em que os nós são expandidos, ou 
seja, retirados da fronteira. 
BUSCA CEGA (não informada) 
● Em Largura 
● Em Profundidade 
● Profundidade Limitada 
● Aprofundamento Iterativo 
 BUSCA EM LARGURA 
Nós são expandidos na ordem em 
que foram criados. 
 
 
 BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
• Completa Se número de ações é finito 
• Ótima Se ações tem custo 1 
 
• Espaço mantém todos os nós na 
memória... 
 
 BUSCA EM PROFUNDIDADE 
O último nó criado é o primeiro a 
ser expandido. 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
• Não é Completa (ramo pode ser 
infinito) 
• Não é ótima (encontra a primeira 
solução e não a de menor custo) 
 
Mas: só guarda nós do caminho atual! 
 
 PROFUNDIDADE LIMITADA 
Coloca um limite l na busca em 
profundidade. Nós de profundidade 
l são considerados como terminais. 
 PROFUNDIDADE ITERATIVA 
Repete a busca com profundidade 
limitada para valores de l cada vez 
maiores. 
Combina vantagens da busca em 
profundidade com a busca em 
largura! 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
• Completa Se número de ações é finito 
• Ótima Se ações tem custo 1 
 
• Espaço mantém apenas o caminho 
atual na memória! 
 
 
 PROFUNDIDADE ITERATIVA 
Repete a busca com profundidade 
limitada para valores de l cada vez 
maiores. 
Combina vantagens da busca em 
profundidade com a busca em 
largura! 
 
INTELIGÊNCIA ARTIFICIAL 
 
Resolução de Problemas 
através de Busca