Upload
dinhnhan
View
215
Download
0
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 ...
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
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
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