29
Prof. Frederico Brito Fernandes [email protected] 1. 1. Busca com Busca com informação informação 2. 2. Busca Gulosa Busca Gulosa 3. 3. Busca A* Busca A* 4. 4. Heurística Heurística 5. 5. Heurística Heurística Admissível Admissível 6. 6. Princípio da Princípio da Dominância Dominância Busca com Busca com Informação 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

Embed Size (px)

Citation preview

Page 1: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Prof. Frederico Brito [email protected]

1.1. Busca com Busca com informaçãoinformação

2.2. Busca GulosaBusca Gulosa3.3. Busca A*Busca A*4.4. HeurísticaHeurística5.5. Heurística Heurística

AdmissívelAdmissível6.6. Princípio da Princípio da

DominânciaDominância

Busca comBusca comInformaçãoInformaçãoBusca comBusca comInformaçãoInformação

Page 2: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 2/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Estudo de Caso: menor caminho

Início

objetivo

Page 3: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 3/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 4: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 4/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Problema: busca de caminho

Início

objetivo

Page 5: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 5/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 6: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 6/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de busca gulosa pela melhor escolha

Page 7: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 7/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de busca gulosa pela melhor escolha

Page 8: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 8/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de busca gulosa pela melhor escolha

Page 9: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 9/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 10: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 10/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Problema: busca de caminho

Início

objetivo

g(Sibiu Fagaras) + h(Fagaras) (99) + (178) = 277km

GULOSO:GULOSO:

g(Sibiu Rimnicu) + h(Rimnicu) (80) + (193) = 273km

IDEAL:IDEAL:

Não considera Não considera o custo g()o custo g()

Page 11: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 11/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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 beco-sem-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

Page 12: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 12/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 13: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 13/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 14: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 14/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 15: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 15/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 16: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 16/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 17: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 17/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 18: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 18/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 19: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 19/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 20: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 20/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 21: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 21/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Exemplo de Busca A*

Page 22: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 22/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Contornos

Page 23: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 23/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 24: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 24/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 25: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 25/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Construindo Funções Heurísticas

• 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

estado inicial estado final

Page 26: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 26/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 27: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 27/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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

Page 28: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 28/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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.

Page 29: Prof. Frederico Brito Fernandes asper@fredbf.com 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

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 29/29Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

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• 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