Inteligência Artificial
Resolução de problemas por meio de busca
Adaptação dos slides disponíveis em [Link] (site do livro
Inteligência Artificial, de Stuart Russel e Peter Norvig).
Estrutura da Apresentação
Formulação do Problema
Problemas Exemplo
Algoritmos de Busca Básicos
Mapa da Romênia
Mapa da Romênia
Férias na Romênia, atualmente em Arad
Voo parte amanhã de Bucareste.
Formulação do Objetivo
Estar em Bucareste.
Formulação do Problema
Estados: as várias cidades.
Ações: dirigir entre cidades.
Solução
Sequência de cidades; e.g. Arad, Sibiu, Fagaras, Bucareste, …
Formulação do Problema
Um problema é definido por quatro itens:
Um Estado Inicial, ex. Em Arad.
Função Sucessora S(x) = conjunto de pares ação-estado
Exemplo. S(Arad)={<Arad → Zerind, Zerind>,…}
Teste de Objetivo, que pode ser
Explícito;
Implícito.
Custo de Caminho
Ex. soma de distâncias, número de ações executadas, etc.
c(x,a,y) é o custo do passo (maior ou igual a 0).
Uma Solução é uma sequência de ações do estado inicial para o
estado objetivo.
Gráfico do Espaço de Estados do
Aspirador de Pó
Quais os estados, ações, meta(s), custo de caminho?
Exemplo: 8-Puzzle
Quais os estados, ações, meta(s), custo de caminho?
Exemplo: 8-Puzzle
Problema pertencente à classe NP-Completa
O quebra cabeça de 8 peças tem 9!/2=181.440
estados acessíveis.
O quebra cabeça de 15 peças (tabuleiro 4 x 4) tem
aproximadamente 1,3 trilhão de estados!
Um quebra cabeças de 24 peças tem cerca de 1025
estados!
Exemplo: Problema das 8 rainhas
Quais os estados, ações, meta(s), custo de caminho?
Em Busca de Soluções
As sequências de ações possíveis que começam a
partir do estado inicial formam uma árvore de
busca com o estado inicial na raiz.
Os ramos são as ações e os nós correspondem ao
espaço de estados.
A figura a seguir apresenta os primeiros passos no
crescimento de uma árvore de busca.
Exemplo: Primeiros Passos de
Crescimento de uma Árvore de Busca
Exemplo: Primeiros Passos de
Crescimento de uma Árvore de Busca
Exemplo: Primeiros Passos de
Crescimento de uma Árvore de Busca
Implementação: nodos vs. estados
Um estado é uma (representação) de uma configuração
física.
Um nó é uma estrutura de dados que contém cinco
componentes: estado, pai, ação, profundidade e custo de
caminho.
Estratégias de Busca
Uma estratégia de busca é definida pela ordem de expansão
dos nós.
Medidas de desempenho para diferentes estratégias:
Completude: Sempre encontra uma solução (se existir)?
Otimalidade: Sempre encontra a solução de menor custo?
Complexidade (tempo): Número de nós gerados/expandidos.
Complexidade (espaço): Máximo número de nós na memória.
Complexidades de tempo e espaço são medidas em termos
de:
b : fator de ramificação máximo da árvore.
d : profundidade do nó objetivo mais raso.
m : profundidade máxima do espaço de estados (pode ser ∞).
Estratégias Não-Informadas
Usam apenas a informação disponível na formulação do
problema.
Estratégias:
Busca em largura;
Busca uniforme;
Busca em profundidade;
Busca em profundidade limitada;
Busca em profundidade iterativa.
Busca em Largura
Expande o nodo não expandido mais raso.
Exemplo:
Busca em Largura
Exemplo:
Busca em Largura
Exemplo:
Busca em Largura
Exemplo:
Busca em Largura
Completude:
– SIM
• Se o nó objetivo mais raso estiver em alguma profundidade
finita d.
• Condição: b finito.
Otimalidade:
– Se o custo do caminho for função não decrescente da profundidade
do nó.
Busca em Largura
Complexidade (tempo)
Número total de nós gerados = b + b2 + b3 + … + bd+
(bd+1-b)
custo exponencial = O (bd+1).
Complexidade(espaço)
custo exponencial = O (bd+1).
Busca de Custo Uniforme
Quando os custos dos passos são iguais, a busca em largura
é ótima.
Com uma simples extensão, é possível encontrar um
algoritmo que é ótimo para qualquer função de custo.
Em vez de expandir o nó mais raso, a busca de custo
uniforme expande o nó n com custo de caminho g(n) mais
baixo.
Busca de Custo Uniforme
S
0 S
A B C S
2 6 20
A A B C
6 20 S
2 10 G
12
S 6 B 5 G A B C
20
20 C 9 G G
12 11
Busca de Custo Uniforme
Fila de Prioridades
– F = {S}
– F = {A, B, C}
– F= {B, GA, C}
– F= {GB, GA, C}
Busca em Profundidade
Expande o nodo não expandido mais profundo.
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Exemplo:
Busca em Profundidade
Completude:
– Não.
– Pode ficar presa explorando um longo (ou até
mesmo infinito) caminho enquanto a solução
pode estar próxima à raiz em outro ramo da
árvore.
Otimalidade:
– Não.
Busca em Profundidade
Complexidade (tempo)
O(bm).
Complexidade (espaço)
O(bm): espaço linear!
Busca em Profundidade Limitada
Limite de profundidade predeterminado l.
Se l < d (não é completa).
Se l > d (não é ótima).
Busca em Profundidade Iterativa
Estratégia que aumenta gradualmente o limite de
profundidade.
Combina os benefícios das buscas em profundidade
e largura.
Como na busca em profundidade, os requisitos de
memória são modestos.
Como na busca em largura, ela é ótima (desde que o
fator de ramificação seja finito e o custo de
caminho seja função não decrescente da
profundidade do nó).
Busca em Profundidade Iterativa
Busca em Profundidade Iterativa
Busca em Profundidade Iterativa
Busca em Profundidade Iterativa
Busca Bidirecional
Duas buscas simultâneas
Referências
Stuart Russel e Peter Norvig, Inteligência
Artificial, 2ª edição, Editora Campus, 2004.