Transcript
Page 1: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Busca HeurísticaProf. Valmir Macário Filho

Page 2: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

2

Busca com informação e exploração

Capítulo 4 – Russell & NorvigSeção 4.1

Estratégias de Busca Exaustiva (Cega)

Page 3: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

3 Estratégias de Busca Exaustiva (Cega)

• São ineficientes na maioria dos casos:▫ Utilizam apenas o custo de caminho do nó atual ao nó

inicial para decidir qual o próximo nó da fronteira a ser expandido.

▫ Essa medida nem sempre conduz a busca na direção do objetivo.

Page 4: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Busca com informação (ou heurística)•Utiliza conhecimento específico sobre o

problema para encontrar soluções de forma mais eficiente do que a busca cega.▫Conhecimento específico além da definição do

problema.

• Aplicam de uma função de avaliação a cada nó na fronteira do espaço de estados:▫ Essa função estima o custo de caminho do nó atual

até o objetivo mais próximo utilizando uma função heurística.

▫ Função heurística: estima o custo do caminho mais barato do estado atual

até o estado final mais próximo.

4

Page 5: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

5

Busca Heurística

• Classes de algoritmos para busca heurística:1. Busca pela melhor escolha (Best-First

search)2. Busca com limite de memória3. Busca com melhora iterativa

Page 6: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Busca pela melhor escolha• Idéia: usar uma função de avaliação f(n) para

cada nó.▫ estimativa do quanto aquele nó é desejávelExpandir nó mais desejável que ainda não foi expandido

• Implementação:▫Insere novos nós na fronteira ordenados

com base na função de avaliação f(n)• Casos especiais:

▫ Busca gulosa pela melhor escolha▫ Busca A*

6

Page 7: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

7

BME: Busca Gulosa

• Semelhante à busca em profundidade com backtracking

• Tenta expandir o nó mais próximo do nó final com base na estimativa feita pela função heurística h

• Função-Avaliação▫ função heurística h

Page 8: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

8

Funções Heurísticas• Função heurística - h

▫estima o custo do caminho mais barato do estado atual até o estado final mais próximo.

• Funções heurísticas são específicas para cada problema

• Exemplo: ▫encontrar a rota mais barata de

Garannhuns a Recife▫hdd(n) = distância direta entre o nó n e o

nó final.

Page 9: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

9

Funções Heurísticas

•Como escolher uma boa função heurística?▫ela deve ser admissível▫i.e., nunca superestimar o custo real da

solução

•Distância direta (hdd) é admissível porque o caminho mais curto entre dois pontos é sempre uma linha reta

Page 10: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Romênia com custos em km

10

Distância em linha reta para Bucareste

Page 11: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca gulosa pela melhor escolha

11

Page 12: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca gulosa pela melhor escolha

12

Page 13: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca gulosa pela melhor escolha

13

Page 14: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca gulosa pela melhor escolha

14

Page 15: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Busca gulosa pela melhor escolha•Não é ótima, pois segue o melhor passo

considerando somente o estado atual.▫ Pode haver um caminho melhor seguindo

algumas opções piores em alguns pontos da árvore de busca.

•Minimizar h(n) é suscetível a falsos inícios.▫Ex. Ir de Iasi a Fagaras

Heurística sugerirá ir a Neamt, que é um beco sem saída. Se repetições não forem detectadas a busca entrará em

loop.

15

Page 16: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Propriedades da busca gulosa pela melhor escolha•Completa? Não – pode ficar presa em

loops, ex., Iasi Neamt Iasi Neamt•Tempo? O(bm) no pior caso, mas uma boa

função heurística pode levar a uma redução substancial

•Espaço? O(bm) – mantém todos os nós na memória

•Ótima? Não

16

Page 17: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

17

BME: Algoritmo A*• A* expande o nó de menor valor de f na

fronteira do espaço de estados• Tenta minimizar o custo total da solução

combinando:▫ Busca Gulosa (h)

econômica, porém não é completa nem ótima

▫ Busca de Custo Uniforme (g) ineficiente, porém completa e ótima

• f - Função de avaliação do A*:▫ f (n) = g (n) + h (n)▫ g (n) = distância de n ao nó inicial▫ h (n) = distância estimada de n ao nó final

Page 18: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

18

Page 19: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

19

Page 20: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

20

Page 21: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

21

Page 22: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

22

Page 23: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Exemplo de busca A*

23

Page 24: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Heurística Admissível•Uma heurística h(n) é admissível se para

cada nó n, h(n) ≤ h*(n), onde h*(n) é o custo verdadeiro de alcançar o estado objetivo a partir de n.

•Uma heurística admissível nunca superestima o custo de alcançar o objetivo, isto é, ela é otimista.

•Exemplo: hDLR(n) (distância em linha reta nunca é maior que distância pela estrada).

•Teorema: Se h(n) é admissível, A* usando algoritmo BUSCA-EM-ARVORE é ótima.

24

Page 25: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

25

Algoritmo A*: Análise do comportamento

• Custo de tempo:▫ exponencial com o comprimento da solução, porém

boas funções heurísticas diminuem significativamente esse custo o fator de expansão fica próximo de 1

• Custo memória: O (bd) ▫ guarda todos os nós expandidos na memória, para

possibilitar o backtracking

Page 26: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Propriedades da Busca A*•Completa? Sim (a não ser que exista uma

quantidade infinita de nós com f ≤ f(G) )•Tempo? Exponencial no pior caso•Espaço? Mantém todos os nós na

memória•Ótima? Sim•Otimamente eficiente

▫Nenhum outro algoritmo de busca ótimo tem garantia de expandir um número de nós menor que A*. Isso porque qualquer algoritmo que não expande todos os nós com f(n) < C* corre o risco de omitir uma solução ótima.

26

Page 27: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Inventando Funções Heurísticas

•Como escolher uma boa função heurística h ?▫h depende de cada problema particular.▫h deve ser admissível

i.e., não superestimar o custo real da solução •Existem estratégias genéricas para definir

h :1) Relaxar restrições do problema2) “Aprender” a heurística pela experiência

Aprendizagem de máquina

27

Page 28: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Estratégias para definir h (1) Relaxando o problema• Problema Relaxado:

▫versão simplificada do problema original, onde os operadores são menos restritivos

• Exemplo: jogo dos 8 números ▫Operador original

um número pode mover-se de A para B se A é adjacente a B e B está vazio

busca exaustiva 322 estados possíveis▫Operadores relaxados:

1. um número pode mover-se de A para B se A é adjacente a B (h2)2. um número pode mover-se de A para B se B está vazio3. um número pode mover-se de A para B (h1)

28

Page 29: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Estratégias para definir h (1) Relaxando o problema

29

Heurísticas para o jogo dos 8 números h1 = no. de elementos fora do lugar (h1=7)h2 = soma das distâncias de cada número à posição final (h2 = 2+3+3+2+4+2+0+2=18)

Page 30: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Estratégias para definir h (1) Relaxando o problema

•O custo de uma solução ótima para um problema relaxado é sempre uma heurística admissível para o problema original.

•Existem softwares capazes de gerar automaticamente problemas relaxados▫Se o problema for definido em uma

linguagem formal•Existem também softwares capazes de

gerar automaticamente funções heurísticas para problemas relaxados

30

Page 31: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Escolhendo Funções HeurísticasÉ sempre melhor usar uma função

heurística com valores mais altos◦ i.e., mais próximos do valor real do custo de

caminho◦** contanto que ela seja admissível **

No exemplo anterior, h2 é melhor que h1◦n, h2(n) h1(n) ◦A* com h2 expande menos nós do que com h1

hi domina hk hi(n) hk(n) n no espaço de estados◦h2 domina h1

31

Page 32: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Escolhendo Funções Heurísticas• Caso existam muitas funções heurísticas para

o mesmo problema,▫ e nenhuma delas domine as outras, ▫ usa-se uma heurística composta:

h(n) = max (h1(n), h2(n),…,hm(n))• Assim definida, h é admissível e domina cada

função hi individualmente• Existem software capazes de gerar

automaticamente problemas relaxados▫ Se o problema for definido em uma linguagem formal

32

Page 33: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Estratégias para definir h (2) Aprendendo a heurística

• Definindo h com aprendizagem automática (1) Criar um corpus de exemplos de

treinamento▫Resolver um conjunto grande de problemas

e.g., 100 configurações diferentes do jogo dos 8 números

▫Cada solução ótima para um problema provê exemplos Cada exemplo consiste em um par (estado no caminho “solução”, custo real da

solução a partir daquele ponto)

33

Page 34: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Estratégias para definir h (2) Aprendendo a heurística

(2) Treinar um algoritmo de aprendizagem indutiva▫Que então será capaz de prever o custo

de outros estados gerados durante a execução do algoritmo de busca

34

Page 35: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Qualidade da função heurística

• Medida através do fator de expansão efetivo (b*)▫b* é o fator de expansão de uma árvore

uniforme com N nós e nível de profundidade d▫N = 1 + b* + (b*)2 + ... + (b*)d , onde

N = total de nós expandidos para uma instância de problema

d = profundidade da solução•Mede-se empiricamente a qualidade de h a

partir do conjunto de valores experimentais de N e d. ▫uma boa função heurística terá o b* muito

próximo de 135

Page 36: Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

Qualidade da função heurística

•Observações:▫Se o custo de execução da função

heurística for maior do que expandir os nós, então ela não deve ser usada.

▫uma boa função heurística deve ser eficiente e econômica.

36


Recommended