4 - Problema de buscas

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