Busca com Informação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estratégias de Busca com informação e exploração
Prof. Pedro Luiz Santos Serra
Prof. Pedro L. S. Serra
2
Introdução
Utiliza o conhecimento específico do problema;
Pode encontrar soluções mais eficientes que uma estratégia sem informações;
Busca pela melhor escolha (Best-First): É uma especialização do algoritmo BUSCA-EM-ÁRVORE, onde:
Um nó é selecionado com base em uma função de avaliação f(n).
Tradicionalmente o nó com avaliação mais baixa (menor distância até o objetivo) é selecionado para expansão.
Pode ser implementada segundo uma estrutura geral de busca por meio de uma fila de prioridades.
Prof. Pedro L. S. Serra
3
Introdução
Existe uma família inteira de algoritmos BUSCA-PELA-MELHOR-ESCOLHA com funções de avaliação diferentes.
Um componente fundamental desses algoritmos é uma função heurística, denotada por h(n).
h(n) = custo estimado do caminho mais econômico do nó n até um nó objetivo
As funções heurísticas são a forma mais comum de aplicar conhecimento adicional do problema ao algoritmo de busca.
Prof. Pedro L. S. Serra
4
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 usando apenas a função heurística: f(n)=h(n)
Exemplo: Localização de rotas na Romênia:
Emprega-se a heurística de distância em linha reta: hDLR. 
Trata-se da distância em linha reta da cidade (ou nó) analisado até a cidade (ou nó) objetivo.
Os valores de hDLR devem ser tabelados e devem passar a compor um dos campos de cada nó.
Prof. Pedro L. S. Serra
5
Busca gulosa pela melhor escolha
Prof. Pedro L. S. Serra
6
Busca gulosa pela melhor escolha
Prof. Pedro L. S. Serra
7
Busca gulosa pela melhor escolha
É semelhante a busca em profundidade:
Segue um único caminho até o objetivo;
Voltará se encontrar um nó sem expansões (ou beco sem saída);
Não é ótima;
É incompleta : pode entrar em um caminho infinito e nunca retornar para experimentar outras possibilidades).
Complexidade de tempo e espaço é O(bm), onde m é a profundidade máxima do espaço de busca.
Com uma boa função heurística, a complexidade da busca gulosa pela melhor escolha pode ter uma redução substancial.
Prof. Pedro L. S. Serra
8
Busca A*
É a forma mais conhecida de busca pela melhor escolha;
Avalia nós combinando:
 g(n)  custo para alcançar cada nó
h(n)  custo para ir do nó até o objetivo
f(n) = g(n) + h(n)
f(n)  custo estimado da solução de custo mais baixo passando por n.
Estratégia  encontrar a solução de custo mais baixo:
Experimentar primeiro o nó com menor valor de g(n) + h(n)
Tal estratégia poderá resultar em um algoritmo ótimo e completo, desde que satisfeita certas condições.
Prof. Pedro L. S. Serra
9
Busca A*
Será ótima se for usada com BUSCA-EM-ÁRVORE e se h(n) for uma heurística admissível.
Heurística admissível: trata-se de uma função heurística que nunca superestime o custo para alcançar o objetivo.
São otimistas por natureza;
Imaginam que o custo da resolução do problema seja menor do que ele é na realidade;
Como g(n) é o custo exato para se alcançar n  f(n) nunca irá superestimar o custo verdadeiro de uma solução passando por n.
Exemplo: Distância de linha reta: hDLR. O caminho mais curto entre dois pontos é uma linha reta, logo, não poderá ser superestimadora.
Prof. Pedro L. S. Serra
10
Busca A*
Prof. Pedro L. S. Serra
11
Busca A*
Atividade
Prof. Pedro L. S. Serra
12
Problemas de locomoção entre cidades podem ser resolvidos por meio de técnicas de busca.
Utilizando as técnicas de busca pela melhor escolha – gulosa e A*
Encontrar o caminho para se locomover do estado A até o estado B.
Avaliar o custo do caminho considerando os seguintes itens:
número de estados visitados
distancia entre os estados
tempo de deslocamento entre estados (considerar 1h para percorrer cada 100 km)
Atividade
Prof. Pedro L. S. Serra
13
DISTANCIAS ENTRE CADA PONTO E O OBJETIVO (EM KM)
A
660
5
410
1
520
6
380
2
510
7
210
3
550
8
220
4
390
9
240