2 1 Resolução de Problemas Busca em Espaço de Estados

Prévia do material em texto

10/03/2015
1
Inteligência Artificial 
Aula: 
Resolução de Problemas
Busca em Espaço de Estados 
DECOM/UFOP
Problemas de busca
• Um problema de busca consiste de:
▫ Espaço de estados
▫ Função Sucessor
▫ Estado inicial, estado(s) objetivo(s) e função de custo
de caminho
• Uma solução é a sequência de ações (plano) para
transformar o estado inicial no estado objetivo.
N, 1
E, 1
2Inteligência Artificial
10/03/2015
2
Formulação do Problema de Busca
Grafo de Estados
3
� Espaço de estados S
� Função sucessor
� Estado inicial
� Estado(s) Objetivo
� Custo de arco
� Solução: 
� caminho
S
1
3 2
Inteligência Artificial
Um problema simples...
• Na Romênia, sair de Arad e chegar em 
Bucareste, de carro.
4Inteligência Artificial
10/03/2015
3
Mais informação...
5Inteligência Artificial
Romênia: Mais informação relevante...
6Inteligência Artificial
10/03/2015
4
Romênia: Problema de Busca
• Espaço de estados:
▫ Cidades
• Successor:
▫ Cidade adjacente
com custo igual
distância
• Estado inicial:
▫ Arad
• Estado objetivo:
Bucharest?
• Solução?
7Inteligência Artificial
Grafo de Estados
• Cada estado é 
representado
por um nó
• Um arco conecta s 
a s’ se e somente se 
s’ ∈ SUCCESSORS(s)
• Pode conter mais de um
componente conexo
8Inteligência Artificial
10/03/2015
5
Solução em Grafo de Estados para o 
Problema de Busca
• Caminho conectando nó que representa estado
inicial a qualquer nó que represente objetivo
9
I
G
Inteligência Artificial
Solução para o Problema de Busca
• O custo do caminho é a soma dos custos das 
arestas.
• Uma solução ótima é o caminho de menor custo.
• Pode não haver solução!
10
I
G
Inteligência Artificial
10/03/2015
6
Buscando no espaço de estados
• Muitas vezes é inviável (ou muito caro) construir
a representação completa do grafo de estados.
11Inteligência Artificial
Buscando no espaço de estados
• O resolvedor de problemas deve construir a 
solução explorando um pequeno pedaço do grafo
de estados…
12Inteligência Artificial
10/03/2015
7
13
Árvore de busca
Buscando no espaço de estados – a 
Árvore de Busca
Inteligência Artificial
14
Árvore de busca
Buscando no espaço de estados – a 
árvore de busca
Inteligência Artificial
10/03/2015
8
Buscando no espaço de estados – a 
árvore de busca
15
Árvore de busca
Inteligência Artificial
16
Árvore de busca
Buscando no espaço de estados – a 
árvore de busca
Inteligência Artificial
10/03/2015
9
17
Árvore de busca
Buscando no espaço de estados – a 
árvore de busca
Inteligência Artificial
18
Árvore de busca
Buscando no espaço de estados – a 
árvore de busca
Inteligência Artificial
Cada nó da árvore de busca corresponde a um caminho no 
grafo de estados.
10/03/2015
10
Tipos de busca
• Clássica: cega ou sem informação
▫ Largura
▫ Profundidade
▫ Profundidade limitada
▫ Aprofundamento Iterativo
▫ Custo Uniforme
▫ Bidirecional
• Clássica: Heurísticas
▫ Melhor primeiro
▫ A*
• Além das clássicas
▫ Busca gulosa
▫ Simulated annealing
▫ Algoritmos genéticos
19Inteligência Artificial
Algoritmo de Árvore de Busca
• Idéias importantes:
▫ Fronteira (ou fringe)
▫ Expansão
▫ Estratégia de exploração
• Principal pergunta: qual o próximo nó da
fronteira a ser explorado?
20Inteligência Artificial
10/03/2015
11
21Inteligência Artificial
Estados vs. Nós
• Nós no grafo de estados são estados
▫ Representam um estado abstrato do mundo
▫ Podem ser objetivo, têm sucessores, podem ter múltiplos predecessores
• Nós nas árvores de busca são planos
▫ Representam o plano (sequência de ações) que levou o mundo para
aquele estado, a partir do inicial.
▫ Tem um estado associado e um pai, tamanho de caminho, profundidade, 
custo.
▫ O mesmo estado pode ser alcançado em diferentes nós da árvore de 
busca
Profundidade 5
Profundidade 6
Pai
Nó
Ação
22Inteligência Artificial
10/03/2015
12
Propriedades de Algoritmos de Busca
• Completo? Garante que acha solução se existe?
• Ótimo? Garante achar o caminho de menor custo?
• Complexidade de tempo?
• Complexidade de espaço?
Variáveis:
n Número de estados (representação)
b Fator médio de ramificação
(número médio de sucessores - expansão)
C* Custo da solução ótima
d Profundidade da solução mais curta
m Maior profundidade da árvore de busca
23Inteligência Artificial
Busca em profundidade
24BCC 325/2012-2
10/03/2015
13
DFS: resumo
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
S
G
d
b
p
q
c
e
h
a
f
r
q
p
h
fd
b
a
c
e
r
Estratégia: expanda
o nó mais
profundo primeiro
Implementação: 
fronteira é pilha
(lista LIFO)
25Inteligência Artificial
DFS
• Completo? Garante que acha solução se existe?
• Ótimo? Garante achar o caminho de menor custo?
• Complexidade de tempo?
• Complexidade de espaço?
Variáveis:
n Número de estados (representação)
b Fator médio de ramificação
(número médio de sucessores - expansão)
C* Custo da solução ótima
d Profundidade da solução mais curta
m Maior profundidade da árvore
26Inteligência Artificial
10/03/2015
14
Avaliação de buscas
…
b
1 node
b nodes
b2 nodes
bm nodes
m níveis para
solução
Algoritmo Completo Ótimo Tempo Espaço
DFS O(bm) O(bm)
27Inteligência Artificial
DFS puro não é completo…
• Como consertar???? Grafo de busca evita
revisitar.
START
GOAL
a
b
28Inteligência Artificial
10/03/2015
15
Resolvendo o problema da completude
ao preço de memória…
• Evitar ciclos – não visitar o mesmo estado no 
caminho
• Evitar caminhos redundantes – não visitar o 
mesmo estado
29
Inteligência Artificial
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
Busca em grafo
30Inteligência Artificial
10/03/2015
16
DFS não garante otimalidade…
• Objetivo alcançado em primeiro lugar depende
da ordem de geração dos sucessores.
• Existe sempre uma estratégia que garante o 
ótimo, mas encontrá-la é equivalente a resolver 
o problema original.
31Inteligência Artificial
Avaliação de buscas em grafo
…
b
1 node
b nodes
b2 nodes
bm nodes
m níveis para
solução
Algoritmo Completo Ótimo Tempo Espaço
DFS Somente 
caminho
S N O(bm) O(bm)
32Inteligência Artificial
10/03/2015
17
Busca em Largura
33BCC 325/2012-2
BFS: resumo
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
S
G
d
b
p q
c
e
h
a
f
r
Camadas
de Busca
Estratégia: expandir o nó
mais raso primeiro
Implementação: Fronteira é 
uma fila FIFO
34Inteligência Artificial
10/03/2015
18
Avaliação de buscas em grafo
Algoritmo Completo Ótimo Tempo Espaço
DFS Com 
caminho
S
BFS
N
…
b
1 nó
b nós
b2 nós
bm nós
d camadas
O(bd) O(bd)
bd nós
35Inteligência Artificial
O(bm) O(bm)
S*S
Ótimo para custo igual
Requisitos de Tempo e Memória
d # Nós Tempo Memória
2 111 .01 msec 11 Kbytes
4 11,111 1 msec 1 Mbyte
6 ~106 1 sec 100 Mb
8 ~108 100 sec 10 Gbytes
10 ~1010 2.8 hours 1 Tbyte
12 ~1012 11.6 days 100 Tbytes
14 ~1014 3.2 years 10,000 Tbytes
36
b = 10; 1,000,000 nós/seg; 100bytes/nó
Inteligência Artificial
10/03/2015
19
BFS: Algoritmo
37Inteligência Artificial