Pesquisa A*
Last updated
Last updated
Escolhe-se o nó em que a função de custo total f(n)=g(n)+h(n) tem o menor valor.
g(n) = custo desde o nó inicial até ao nó n.
h(n) = custo estimado desde o nó n até à solução [heurística].
A função heurística h(n) diz-se admissível se nunca sobrestima o custo real de chegar a uma solução a partir de n.
Se for possível garantir que h(n) é admissível, então a pesquisa A* encontra sempre (um)a solução óptima.
A pesquisa A* é também completa.
A pesquisa A* foi inventada em 1968 para optimizar o planeamento de caminhos deste robô.
h(n) = 0
f(n) = g(n)
É um caso particular da pesquisa A*
Também conhecido como algoritmo de Dijkstra.
Tem um comportamento parecido com o da pesquisa em largura.
Caso exista solução, a primeira solução encontrada é óptima.
Ignora custo acumulado g(n)
f(n) = h(n)
Dado que o custo acumulado é ignorado, não é verdadeiramente um caso particular da pesquisa A*
Tem um comportamento que se aproxima da pesquisa em profundidade.
Ao ignorar o custo acumulado, facilmente deixa escapar a solução óptima.
Em inglês: “graph search”.
Frequentemente, o espaço de estados é um grafo.
Ou seja, transições a partir de diferentes estados podem levar ao mesmo estado.
Isto leva a que a pesquisa fique menos eficiente.
Portanto, o que se deve fazer é memorizar os estados já visitados por forma a evitar tratá-los novamente.
Memoriza-se apenas o melhor caminho até cada estado.
Tal como no algoritmo anterior, trabalha-se com uma fila de nós
Chama-se fila de nós ABERTOS (nós ainda não expandidos, ou folhas).
Em cada iteração, o primeiro nó em ABERTOS é seleccionado para expansão.
Adicionalmente, usa-se também uma lista de nós FECHADOS (os já expandidos).
Necessário para evitar repetições de estados.
Inicialização
N0 <- nó do estado inicial; ABERTOS <- { N0 }
FECHADOS <- { }
Se ABERTOS = {}, então acaba sem sucesso.
Seja N o primeiro nó de ABERTOS.
Retirar N de ABERTOS.
Colocar N em FECHADOS.
Se N satisfaz o objectivo, então retornar a solução encontrada.
Expandir N:
CV <- conjunto dos vizinhos sucessores de N.
Adicionar os novos nós a ABERTOS.
Reordenar ABERTOS
Voltar ao passo 2.
Tal como a pesquisa em árvore, a “pesquisa em grafo” ou “graph search” utiliza uma árvore de pesquisa.
No entanto, a pesquisa em árvore normal ignora a possibilidade de o espaço de estados ser um grafo.
Mesmo que o espaço de estados seja um grafo, a pesquisa em árvore trata-o como se fosse uma árvore.
Pelo contrário, a pesquisa em grafo leva em conta que o espaço de estados é normalmente um grafo e garante que a árvore de pesquisa não tem mais do que um caminho para cada estado.
Uma heurística é tanto melhor quanto mais se aproximar do custo real.
A qualidade de uma heurística pode ser medida através do factor de ramificação efectiva.
Quanto melhor a heurística, mais baixo será esse factor.
Em alguns domínios, há funções de estimação de custos que naturalmente constituem heurísticas admissíveis.
Exemplo: Distância em linha recta no domínio dos caminhos entre cidades.
Em muitos outros domínios práticos, não há uma heurística admissível que seja óbvia.
Exemplo: Planeamento no mundo dos blocos.
Um problema simplificado (relaxed problem) é um problema com menos restrições do que o problema original:
É possível gerar automaticamente formulações simplificadas de problemas a partir da formulação original.
A resolução do problema simplificado será feita usando pouca ou nenhuma pesquisa.
Pode-se assim “inventar” heurísticas, escolhendo a melhor, ou combinando-as numa nova heurística.
IMPORTANTE: O custo de uma solução óptima para um problema simplificado constitui uma heurística admissível para o problema original.
Se tivermos várias heurísticas admissíveis (h1, ..., hn), podemos combiná-las numa nova heurística:.
H(n) = max({h1(n), ..., hn(n)}).
Esta nova heurística tem as seguintes propriedades:
Admissível.
Dado que é uma melhor aproximação ao custo real, vai ser uma heurística melhor do que qualquer das outras.
Principais vantagens.
Completa.
Óptima.
Principais desvantagens.
Na maior parte das aplicações, o consumo de memória e tempo de computação têm um comportamento exponencial em função do tamanho da solução.
Em problemas mais complexos, poderá ser preciso utilizar algoritmos mais eficientes, ainda que sacrificando a optimalidade.
Ou então, usar heurísticas com uma melhor aproximação média ao custo real, ainda que não sendo estritamente admissíveis, e não garantindo portando a optimalidade da pesquisa.
Para cada , ligá-lo ao antecessor directo, N.
Para cada , ligá-lo a N caso o melhor caminho passe por N.
