Busca com
Informação
Prof. Frederico Brito Fernandes
[email protected]
1. Busca com
informação
2. Busca Gulosa
3. Busca A*
4. Heurística
5. Heurística
Admissível
6. Princípio da
Dominância
Estudo de Caso: menor caminho
Início
objetivo
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
2/29
Busca pela melhor escolha
• Utiliza uma função de avaliação para cada nó que estima
“o quão desejável” é aquele nó
– Expande o nó que parece mais desejável ainda não expandido
• A fronteira (fila de nós gerados mas não expandidos) será
uma fila ordenada em ordem decrescente de
“desejabilidade”.
• Casos especiais:
– Busca gulosa pela melhor escolha (greedy)
– Busca A*
• Todos os algoritmos de busca pela melhor escolha utilizam
uma função heurística h(n)
– h(n) é o custo estimado do caminho mais econômico do nó n até um nó
objetivo
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
3/29
Problema: busca de caminho
Início
objetivo
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
4/29
Busca gulosa pela melhor escolha
• Minimizar o custo estimado par alcançar o objetivo
• Muitas vezes o custo para se alcançar o objetivo pode ser
estimado mas não pode ser determinado exatamente
• A busca gulosa pela melhor escolha (greedy) expande o nó
que aparenta estar mais próximo do objetivo
• Função de Avaliação utiliza somente h(n)
– Para o exemplo da Romênia:
• hDLR(n) = distância em linha reta de n até Bucarest.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
5/29
Exemplo de busca gulosa pela melhor escolha
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
6/29
Exemplo de busca gulosa pela melhor escolha
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
7/29
Exemplo de busca gulosa pela melhor escolha
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
8/29
Exemplo de busca gulosa pela melhor escolha
• O solução encontrada não é a solução ótima.
• Arad  Sibiu  Fagaras  Bucharest
(140) + (99) + (211) = 450km
• A Solução ótima passa por Rimnicu Vilcea
• Arad  Sibiu  Rimnicu Vilcea  Pitesti Bucharest
(140) + (80)
+
(97) + (101) = 418km
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
9/29
Problema: busca de caminho
GULOSO:
g(Sibiu  Fagaras) + h(Fagaras)
(99)
+
(178)
= 277km
Não considera
o custo g()
Início
objetivo
IDEAL:
g(Sibiu  Rimnicu) + h(Rimnicu)
(80)
+
(193)
= 273km
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
10/29
Análise da busca gulosa pela melhor escolha
• Tende a encontrar soluções rapidamente mas nem
sempre encontra a solução ótima
• Se um dos nós mais próximos da solução é um becosem-saída, então nós serão expandidos sem necessidade
• Se não tomarmos cuidado com os estados repetidos a
solução nunca será encontrada
• Sofre dos mesmos problemas da busca em profundidade
– Segue somente um caminho, mas tem que voltar se não encontrar a
solução
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
11/29
Análise da busca gulosa pela melhor escolha
• Não é ótima nem completa – porque pode entrar
em um caminho infinito
• Complexidade de tempo: O(bm), mas uma boa
heurística pode melhorar muito
• Complexidade de espaço: O(bm), mantém todos os
nós na memória)
* Onde m é a profundidade máxima e b é o fator de ramificação do espaço
de busca.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
12/29
Busca pelo custo mínimo do caminho
A*
• Busca gulosa
– minimiza o custo estimado de n até o objetivo => h(n)
– Não é completa nem ótima
• Busca por custo uniforme
– minimiza o custo do caminho da raiz até n => g(n)
– É completa e ótima – mas analisa muitos nós
• Idéia de A*: combinar as duas estratégias
– Evitar expandir caminhos que já são caros
– Função de Avaliação f(n) = g(n) + h(n)
• f(n) = custo estimado total da solução de custo mais baixo passando por n
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
13/29
Busca pelo custo mínimo do caminho
A*
• É completa e ótima, se h(n) é uma heurística admissível
e consistente (monotônica)
• Heurística admissível:
– h(n) ≤ h’(n)+ custo real de n até n'
– Assim, f(n) nunca superestima o custo atual da melhor solução até n.
– Ao longo de qualquer caminho a partir da raiz, f nunca decresce
– Por exemplo:
• hDLR(n) nunca superestima a distância real pela estrada.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
14/29
Exemplo: busca do caminho mínimo
• Problema:
– Ir de Arad  Bucharest.
• Função heurística:
– Distância em linha reta entre a cidade n e Bucharest.
– Satisfaz a condição de admissibilidade, pois não existe
distância menor entre dois pontos do que uma reta.
– É uma boa heurística, pois induz o algoritmo a atingir o
objetivo mais rapidamente.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
15/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
16/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
17/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
18/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
19/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
20/29
Exemplo de Busca A*
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
21/29
Contornos
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
22/29
Propriedades de A*
• Completa?:
– Sim, a menos que haja uma quantidade infinita de nós com f ≤
f(objetivo)
• Tempo?:
– Exponencial em relação ao comprimento da solução
• Espaço?:
– Mantém todos os nós na memória
• Ótima?:
– Sim, não pode expandir fi+1 antes de fi ser expandido
• Não é prático para muito problemas de grande escala
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
23/29
Heurísticas admissíveis
• h(n) nunca deve superestimar o menor caminho, desta forma
h(n) deve ser sempre menor que o caminho real.
– Isto é, h(n)  h*(n) onde h*(n) é o custo real de n.
• As heurísticas admissíveis tem natureza otimista, pois elas
sempre indicam que o custo da solução é melhor do que ele
realmente é.
• Desta maneira se uma solução ainda não foi encontrada
sempre existirá um nó com f(n) menor do que ela.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
24/29
Construindo Funções Heurísticas
estado inicial
estado final
• Exemplo de heurísticas para o 8-puzzle
– h1(n) = número de quadrados em locais errados
– h2(n) = distância Manhattan total => número de espaços que deve
ser movido para chegar no local correto
– h1(s) = 7 (só o número 7 está no local correto)
– h2(s) = 2+3+3+2+4+2+0+2 = 18
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
25/29
Dominância
• Se h2(n)  h1(n) para todo n (ambas admissíveis)
então h2 domina h1 e é melhor para a busca.
• Isto se reflete diretamente no números de nós
expandidos para cada heurística
• Custos típicos de busca:
– d = 14
• Aprofundamento Iterativo = 3.473.941 nodos
• A*(h1) = 539 nodos
• A*(h2) = 113 nodos
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
26/29
Dominância
• d = 24
• Aprofundamento Iterativo  54.000.000.000
• A*(h1) = 39.135 nodos
• A*(h2) = 1.641 nodos
• Disponibilidade de uma coleção de heurísticas admissíveis
onde nenhuma domina a outra
– Para cada nó n escolha: h(n) = max(h1(n),
h2(n),...,hm(n)), onde h(n) é admissível e domina as
outras heurísticas em n
• Sempre é melhor utilizar uma heurística com valores mais
altos, desde que ela seja admissível
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
27/29
Relaxação de problemas
• Várias vezes "relaxar" (tirar restrições) do problema
pode resultar em uma boa heurística.
• Heurísticas admissíveis podem ser derivadas do custo
de uma solução exata a partir de uma versão relaxada
do problema.
– Se as regras do 8-puzzle forem relaxadas para que um
quadrado possa se mover para qualquer lugar, então h1(n) dá a
solução de caminho mais curto.
– Se as regras forem relaxadas para que um quadrado possa
mover-se para qualquer quadrado adjacente, mesmo que ele
esteja ocupado, então h2(n) dá a solução com caminho mais
curto.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
28/29
Relaxação de problemas
•
•
Ponto chave: o custo da solução ótima de um problema relaxado não
é maior que o custo da solução ótima do problema real. Portanto ela é
uma heurística admissível.
Geração automática de heurísticas
–
Descrição em linguagem formal do 8-puzzle:
•
Um bloco pode se mover do quadrado A para o quadrado B se:
–
–
A é horizontal ou verticalmente adjacente a B e B é vazio
Heurísticas:
(a) Um bloco pode se mover do quadrado A para o B se A é adjacente a B
(b) Um bloco pode se mover do quadrado A para o B se B está vazio
(c) Um bloco pode se mover do quadrado A para o B
–
Programa ABSOLVER
•
•
Disciplina: Inteligência Artificial
Gerou a melhor heurística do 8-puzzle das pré-existentes
Descobriu a primeira heurística útil para o famoso quebra-cabeça do cubo de
ubik
Professor: Frederico Brito Fernandes
29/29