63
Estratégias de Busca Cega Encontram soluções para problemas pela geração sistemática de novos estados, que são comparados ao objetivo. São ineficientes na maioria dos casos: utilizam apenas o custo de caminho do nó atual ao nó inicial (função g(n)) para decidir qual o próximo nó da fronteira a ser expandido. Essa medida nem sempre conduz a busca na direção do objetivo.

Estratégias de Busca Cega - paginapessoal.utfpr.edu.brpaginapessoal.utfpr.edu.br/kathya/Disciplinas/sistemas_inteligentes... · Os primeiros três níveis do espaço de estados do

Embed Size (px)

Citation preview

Estratégias de Busca Cega

• Encontram soluções para problemas pela geração sistemática de novos estados, que são comparados ao objetivo.

• São ineficientes na maioria dos casos:

– utilizam apenas o custo de caminho do nó atual ao nó inicial

(função g(n)) para decidir qual o próximo nó da fronteira a ser

expandido.

– Essa medida nem sempre conduz a busca na direção do

objetivo.

Estratégias de Busca Heurística

• Utilizam conhecimento específico do problema que

pode ser usada para guiar o processo de busca.

• Aplicam uma função que avalia a um nó particular e prediz a qualidade dos seus nós sucessores: – A função avaliação f(n) estima o custo de caminho do nó

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

– A função heurística h(n) estima o custo do caminho mais barato do estado atual até o estado final mais próximo.

f(n) = g(n) + h(n)

Busca Heurística

• Os problemas de IA empregam heurísticas, basicamente, em duas

situações:

1. Um problema pode não ter uma solução exata por causa das ambiguidades inerentes na sua formulação ou pela disponibilidade dos dados. Exemplos: Diagnóstico médico, Sistemas de visão.

2. Um problema pode ter uma solução exata, mas o custo computacional para encontrá-la pode ser proibitivo. Exemplo: Jogo de xadrez.

Busca Heurística • Uma heurística é apenas uma conjectura informada

sobre o próximo passo a ser tomado na solução de um problema.

• A heurística é baseada na experiência e na intuição.

• Uma heurística pode levar um algoritmo de busca a uma solução sub-ótima ou, inclusive, levá-lo a não conseguir encontrar uma solução.

• As heurísticas podem falhar.

George Polya define heurística como “o estudo dos métodos e das regras de

descoberta e invenção” (Polya, 1945) – relacionada com o termo grego original, o

verbo eurisco (“Eu descubro”). Quando Arquimedes emergiu de seu famoso banho

segurando a coroa de ouro, ele gritou “Eureka!” (“Eu descobri!”).

5

Busca Heurística – Exemplo ... Porção do espaço de estados para o jogo-da-velha

9

8

7

.

.

.

N0 de

caminhos

= 9!

6

Busca Heurística – Exemplo ...

Os primeiros três níveis do espaço de estados do jogo-da-velha reduzidos por simetria.

3 movimentos iniciais:

•Para o canto

•Para o centro de um lado

•Para o centro da grade

• A heurística do “maior número de vitórias” aplicada aos primeiros filhos do jogo-da-velha.

Maior número de vitórias: maior número de linhas, colunas e diagonais ainda disponíveis.

Busca Heurística – Exemplo ...

8

Espaço de estados reduzido heuristicamente para o jogo-da-velha.

Busca Heurística – Exemplo

Busca Heurística

• Classes de algoritmos para Busca Heurística:

1. Busca pela melhor escolha (Best-First search):

• Greedy best-first search (Busca gulosa pela melhor escolha)

• A*

2. Busca com limite de memória (Memory Bounded Search):

• IDA* (Iterative Deepening A*)

• RBFS (Busca recursiva de melhor escolha)

• SMA* (Simplified Memory-Bounded A*)

Busca Heurística

• Algoritmo geral: Busca pela Melhor Escolha - BME (Best-first search)

– Seleciona para expansão o nó que tiver o menor custo estimado até a meta (objetivo), segundo uma função de avaliação f(n).

– Tipicamente f(n) usa uma função heurística h(n) = custo estimado do caminho mais econômico do nó n até um nó objetivo (Restrição inicial: se n é um nó objetivo, h(n) = 0).

Busca Heurística

• Uma forma de uso da informação heurística sobre um problema consiste em computar estimativas numéricas para os nós no espaço de estados;

• Uma estimativa indica o quanto um nó é promissor com relação ao alcance de um nó-objetivo;

• A ideia é continuar a busca sempre a partir do nó mais promissor no conjunto de candidatos;

• O programa de busca do melhor caminho (escolha) é baseado neste princípio.

Busca Heurística

• A Busca do melhor caminho pode ser derivada de um refinamento da busca em largura.

• A Busca em largura sempre escolhe para expansão os menores caminhos-candidatos (isto é, os nós extremos menos profundos da busca).

• A Busca do melhor caminho refina este princípio calculando uma estimativa heurística para cada candidato e escolhe para expansão o melhor candidato de acordo com esta estimativa.

Busca Heurística

• Greedy best-first search (Busca gulosa pela melhor escolha)

• Tenta expandir o nó mais próximo à meta, na suposição de que isso provavelmente levará a uma solução rápida.

• Avalia nós para expandir com base unicamente na função heurística: f(n) = h(n)

• Exemplo: encontrar a melhor rota (rota mais curta) de uma

cidade a outra, num mapa usando a Função heurística hDLR(n) (DLR: distância em linha reta entre as cidades e a cidade-meta).

14

Busca Heurística Exemplo: Localização de rotas na Romênia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Um mapa rodoviário simplificado de parte da Romênia.

Busca Heurística Exemplo: Localização de rotas na Romênia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurística de

distância em linha reta hDLR. Os nós são identificados por seus valores de h.

Exemplo – Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurística de

distância em linha reta hDLR. Os nós são identificados por seus valores de h.

Exemplo – Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurística de

distância em linha reta hDLR. Os nós são identificados por seus valores de h.

Exemplo – Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurística de

distância em linha reta hDLR. Os nós são identificados por seus valores de h.

Exemplo – Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurística de

distância em linha reta hDLR. Os nós são identificados por seus valores de h.

Busca Heurística

Busca pela melhor escolha - Busca Gulosa • Não é completa

– Pode entrar em ciclos e não encontrar a solução se não detectar estados repetidos;

– Pode se perder em um caminho infinito e nunca retroceder para tentar outras opções.

• Não é ótima

– No exemplo encontrou caminho (Arad, Sibiu, Fagaras, Bucareste) que é 32km maior que (Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucareste)

– Dependendo do problema e da qualidade da heurística a complexidade pode ter uma redução substancial.

Busca Heurística

• BME mais “famoso”: Busca A*

• Objetivo: Minimizar o custo total estimado da solução.

• Função de avaliação: f(n) = g(n) + h(n) – g(n) = custo do caminho (distância) do nó inicial ao nó n – h(n) = custo estimado do caminho (distância ) de menor custo de n

ao nó final – f(n) = custo estimado da solução de menor custo que passa por n.

• A* expande o nó de menor valor de f na fronteira do espaço de

estados.

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Um mapa rodoviário simplificado de parte da Romênia.

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurística Exemplo: Localização de rotas na Romênia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Exemplo – Passo a Passo ...

Exemplo – Passo a Passo ...

Exemplo – Passo a Passo ...

Exemplo – Passo a Passo ...

Exemplo – Passo a Passo ...

Exemplo – Passo a Passo

38

Estágios em uma busca

A* por Bucareste. Os

nós estão rotulados

f = g + h. Os valores de

h são distâncias em

linha reta para

Bucareste.

Busca Heurística

• A função heurística h(n) deve satisfazer as seguintes condições, para que a busca A* seja ótima:

– Admissibilidade.

– Consistência

Busca Heurística Admissibilidade

• Uma heurística é admissível se nunca superestima o custo de atingir o objetivo.

• Como g(n) é o custo real para atingir n ao longo do caminho atual e

f(n) = g(n)+h(n)

então f(n) nunca irá a superestimar o verdadeiro custo de uma solução ao longo do caminho atual através de n

• A distância em linha reta é uma heurística admissível, pois, o caminho mais curto entre dois pontos quaisquer é uma linha reta

Um algoritmo de busca que garantidamente encontre um percurso ideal para um objetivo, se este existir, é chamado de admissível (Nilsson, N. K. Principles of Artificial Intelligence, Morgan-Kaufmann, 1980).

• h(n) é o estimador, se ele for perfeito então A* convergirá imediatamente para o objetivo

• Se o valor de h(n) for sempre zero, a busca será controlada por g(n).

• Se o valor de g(n) também for zero, a estratégia da busca será aleatória.

• Se o valor de g(n) sempre for 1, a busca será em amplitude

• E se h(n) não for nem perfeito nem zero? – O algoritmo A* encontrará o caminho ideal (determinado por

g(n)) para o objetivo, se este existir, desde que se garanta que h(n) não superestime o custo da busca.

Busca Heurística Admissibilidade

• Para cada nó está indicado f(n) = g(n)+h(n)

• Ao subestimar f(B) jogam-se fora os esforços

• Mas, foi descoberto que B estava distante do objetivo e voltou-se

para experimentar outro percurso.

Busca Heurística Admissibilidade

• O algoritmo expandiu até G para obter um caminho de solução cujo comprimento é 4.

• Supondo que exista um caminho direto de D até uma solução, dando um caminho de comprimento 2, este nunca será encontrado, pois f(D) foi superestimado.

• Ao superestimar f(D), se fez parecer D tão ruim que se pode encontrar uma outra solução, pior, sem nunca expandir D.

Busca Heurística Admissibilidade

Busca Heurística Consistência

• Uma heurística h(n) será consistente se, para cada nó n e para cada sucessor n’ de n gerado por uma ação a, o custo estimado de alcançar o objetivo de n não for maior do que o custo do passo de chegar a n’ mais o custo estimado de alcançar o objetivo de n’

• Desigualdade triangular: cada um dos lados de um triangulo não pode ser mais longo que a soma dos outros dois lados.

)'()'()( n h n,a,n c nh

Busca Heurística Consistência

• Exemplo:

A distancia em linha reta h(n) de Neamt a Urzeni (objetivo) não é maior que o custo g(n) de Neamt a Iasi + custo h(n’) de Iasi a Urzeni, portanto a heurística é consistente.

Busca Heurística

Desempenho do A*

• A* é completa e ótima: nenhum outro algoritmo ótimo garante expandir menos nós que A*.

• A* expande todos os nós com f(n) C* – C* é o custo do caminho de solução ótima

• A* pode expandir alguns nós no “contorno objetivo” (f(n) = C*) antes de selecionar um nó objetivo.

Busca Heurística

Desempenho do A*

• Custo de tempo:

– Crescimento exponencial do número de nós com o comprimento da solução(complexidade temporal).

• Custo memória: O (bd)

– O maior problema é a complexidade espacial, guarda todos os nós gerados na memória, para possibilitar o backtracking.

• Assim, A* não é aplicável em muitos problemas de grande escala. Usa-se variantes que encontram soluções subótimas.

A* define Contornos

f(n) C* , nós no interior de um contorno dado tem custos de f menores ou iguais ao valor de contorno.

Busca Heurística Para reduzir os requisitos de memória para A* adapta-se a ideia de profundidade iterativa para o contexto de busca heurística :

IDA* (Iterative Deepening A*)

Igual ao profundidade iterativa, porém seu limite é dado pela função de avaliação ou f-custo (g+h) , e não pela profundidade (d).

Busca Heurística

– IDA* (Iterative Deepening A*)

• igual ao profundidade iterativa, porém seu limite é dado pela função de avaliação ou f-custo (g+h) , e não pela profundidade (d).

• A cada iteração, o valor de corte é o menor f-custo de qualquer nó que excedeu o corte na iteração anterior.

• Prático para problemas com custos de passo unitário.

• Tem a mesmas dificuldades dos custos de valor real que a versão iterativa de custo uniforme.

Busca Heurística

• RBFS (Busca recursiva de melhor escolha)

– Algoritmo recursivo simples, tenta imitar a operação de busca pela melhor escolha (BFS), mas usando apenas um espaço linear de memória

– Estrutura similar ao de busca em profundidade – Ao invés de continuar indefinidamente

seguindo o caminho atual, utiliza a variáveis f-limite para acompanhar o f-valor do melhor caminho alternativo disponível de qualquer nó ancestral do nó atual

Busca Heurística

• RBFS (Busca recursiva de melhor escolha)

– Se o nó atual exceder esse limite, a recursão reverte para o caminho alternativo

– Com a reversão da recursão, substitui o f-valor de cada nó ao longo do caminho por um valor de backup “o melhor f-valor de seus filhos”

– O RBFS lembra o f-valor das melhores folhas da sub-árvore esquecida e pode, portanto, decidir se vale a pena re-expandir a sub-árvore algum tempo mais tarde

RBFS (Busca recursiva de melhor escolha)

RBFS (Busca recursiva de melhor escolha)

RBFS (Busca recursiva de melhor escolha)

A RBFS é mais eficiente do que a IDA*, mas também tem a geração excessiva de um mesmo nó. Ambas sofrem por usarem pouca memória e ‘esquecem’ o que fizeram. • SMA* (Simplified Memory-Bounded A*)

– Similar ao A*, expande a melhor folha até que a memória esteja cheia

– Como não pode adicionar novo nó, suprime o ‘pior’ nó folha

– O RBFS faz o backup do nó esquecido em seu pai. – O ancestral de uma subárvore esquecida conhece

a qualidade do melhor caminho daquela subárvore.

– Com essa informação, o SMA* regenera a subárvore somente quando todos os outros caminhos foram mostrados como piores do que o caminho que ele esqueceu.

Busca Heurística

Busca Heurística

• Solução de problemas usando técnicas de busca heurística: – dificuldades em definir e usar a função de avaliação – não consideram conhecimento genérico do mundo (ou

“senso comum”)

• Função de avaliação: compromisso (conflito) entre

– tempo gasto na seleção de um nó e – redução do espaço de busca

• Achar o melhor nó a ser expandido a cada passo pode

ser tão difícil quanto o problema da busca em geral.

Busca Heurística

Como escolher uma boa função heurística h?

• h depende de cada problema particular.

• h deve ser admissível – não superestimar o custo real da solução

• Exemplo: jogo dos 8 números – um número pode mover-se de A para B se A é adjacente a B e B

está vazio

– busca exaustiva: • solução média em 22 passos

• fator de ramificação médio: 3

• ≈ 322 estados possíveis

• ≈ 9!/2 (controlando os estados repetidos)

4 5 8

1 6

7 2 3

Busca Heurística

Algumas heurísticas possíveis:

• h1 = n0 de elementos em posições erradas

• h2 = soma das distâncias de cada elemento à posição final - objetivo (city block distance - Manhattan distance)

h1 = 8

h2 = 3+1+2+2+2+3+3+2=18

Distância de Manhattan: distância de quarteirões ou distância de táxi. Recebeu o nome pois define a menor distância possível que um carro é capaz de percorrer numa malha urbana reticulada ortogonal, como se encontram em zonas como Manhattan.

60

• Espaço de estados gerado com h1 (n)

(para cada estado está indicado entre parênteses o valor da função heurística):

Exemplo:

Estado Inicial

Estado Objetivo

2 8 3

1 6 4

7 5

1 2 3

8 4

7 6 5

2 8 3

1 6 4

7 5

(4)

2 8 3

1 6 4

7 5

(6)

2 8 3

1 4

7 6 5

(3)

2 8 3

1 6 4

7 5

(5)

2 8 3

1 4

7 6 5

(4)

2 3

1 8 4

7 6 5

(3)

2 8 3

1 4

7 6 5

(3)

2 8 3

7 1 4

6 5

(4)

8 3

2 1 4

7 6 5

(3)

2 3

1 8 4

7 6 5

(4)

2 3

1 8 4

7 6 5

(2)

1 2 3

8 4

7 6 5

(1)

1 2 3

8 4

7 6 5

(0)

1 2 3

7 8 4

6 5

(2) Neste exemplo não são considerados os nós que aparecem por mais de uma vez.

61

• Espaço de estados gerado com h2 (n)

Exemplo:

Estado Inicial

Estado Objetivo

2 8 3

1 6 4

7 5

1 2 3

8 4

7 6 5

2 8 3

1 6 4

7 5

(5)

2 8 3

1 6 4

7 5

(6)

2 8 3

1 4

7 6 5

(4)

2 8 3

1 6 4

7 5

(6)

2 8 3

1 4

7 6 5

(5)

2 3

1 8 4

7 6 5

(3)

2 8 3

1 4

7 6 5

(5)

2 3

1 8 4

7 6 5

(4)

2 3

1 8 4

7 6 5

(2)

1 2 3

8 4

7 6 5

(1)

1 2 3

8 4

7 6 5

(0)

1 2 3

7 8 4

6 5

(2)

• No exemplo anterior: h2 domina h1 ,

Isso pode ser traduzido na forma: A heurística 2 é melhor que a heurística 1, pois terá um menor fator de ramificação. Desde que h1 e h2 não superestimem o custo real.

Busca Heurística

estados de espaço no , domina n (n) h(n) hh h kiki

Busca Heurística

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