Procura Heuristica
Se soubermos informações úteis sobre o objetivo, podemos usá-las para procuras mais eficientes. As estratégias de procura informada baseiam-se na procura melhor primeiro, utilizando uma função de avaliação f(n) para escolher a ordem de expansão dos nós.
A função de avaliação estima o custo entre um nó, n, e o objetivo. Ela pode incluir:
- g(n): custo do caminho desde o estado inicial até n;
- h(n): estimativa do custo do melhor caminho de n ao objetivo;
- h*(n): custo real do melhor caminho de n ao objetivo.
Chamamos h(n) de função heurística.
Função Heurística
Uma função heurística estima o quão perto um estado está do nó objetivo, como um detetor de metais que apita mais alto à medida que nos aproximamos do objetivo.
Funções heurísticas são estimativas e não representações fiéis do custo real, mas aproximações feitas idealmente por defeito.
Se estivermos num nó objetivo, a função heurística deve ser nula (h(n) = 0).
Procura Melhor Primeiro
A procura melhor primeiro utiliza uma função de avaliação que estima a proximidade de cada nó ao objetivo. Expandimos o nó com o menor valor de f(n) na fronteira, pois idealmente ele nos aproxima do objetivo de forma ótima. Ordenar os nós na fronteira por ordem crescente (minimizar) ou decrescente (maximizar) da função de avaliação
Esta abordagem é semelhante à procura custo uniforme, onde f corresponde ao custo do caminho percorrido. Assim, na procura melhor primeiro, temos f(n) = g(n).
Procura Sôfrega
Na procura sôfrega, usamos apenas a função heurística h(n) para escolher a ordem de expansão dos nós. Assim, temos:
f(n) = h(n)
A procura sôfrega é incompleta pois pode ficar presa em ciclos e não ótima tem termos espaciais é \(O(b^m)\) e temporais \(O(b^m)\).
Procura A*
O algoritmo A* é uma generalização da procura sôfrega e da procura melhor primeiro. A ideia-base da procura é evitar expandir caminhos que já sabemos que terão custos demasiado elevados, considerando tanto o que ficou para trás como o que ainda devemos ter de percorrer para a frente. Se pensarmos bem, f corresponderá então ao custo total estimado da solução mais barata que passa por n. Tal como na procura Sôfrega, vamos manter a fronteira como uma min priority queue, ordenada de forma crescente pelo valor da função de avaliação de cada nó. A função de avaliação é a soma da função de custo do caminho percorrido e da função heurística:
f(n) = g(n) + h(n)
Assim, o A* é completo e ótimo se a função heurística for admissível e consistente.
Utilizar heurísticas admissíveis só torna A∗ ótima na procura em árvore, na procura em grafo, não adicionamos à fronteira estados por onde já passámos, pelo que podemos eventualmente perder o caminho mais curto até ao objetivo.
Função Heurística Admissível
Uma função heurística é admissível se nunca superestimar o custo para alcançar o objetivo.
Ou seja, se h(n) é sempre menor ou igual ao custo real h*(n) para alcançar o objetivo a partir de n.Função Heurística Consistente
Uma heurística é consistente se para todo o nó n e todo o seu sucessor n’, gerado pela ação a,
\( h(n) \leq c(n, a, n') + h(n') \)
onde c(n,a,n′) corresponde ao custo associado a realizar a ação aa de n para n′.
De forma mais simples, uma heurística diz-se consistente se, para todo o nn, para todos os seus sucessores n′ gerados por ações a, o custo estimado de ir de nn ao objetivo for menor ou igual ao custo real de ir de n a n′ somado ao custo estimado de ir de n′ ao objetivo.
Toda a heurística consistente é admissível, mas não podemos afirmar o contrário.
Comparar heurísticas
Seria agora interessante comparar h1 e h2, para procurar perceber qual das duas acaba por dar maiores ganhos de desempenho em procuras. Uma maneira bastante comum de fazer esta comparação é recorrendo a b∗, o effective branching factor da árvore de procura, já que este acaba por ser relativamente consistente para problemas suficientemente difíceis. Dizemos que heurísticas são tanto melhores quanto mais o seu b∗ se aproximar de 1, já que dessa forma estamos efetivamente a dizer que para atingir a "solução média" do problema praticamente não temos de fazer branching (ou pouco), havendo, portanto, menos caminhos alternativos a ser explorados: com uma heurística ideal, teríamos b∗=1 e a árvore de procura seria apenas um ramo contínuo.
Dominância
Uma heurística \(h_1\) domina outra heurística \(h_2\) se \(h_1(n) \geq h_2(n)\) para todo o nó \(n\). Uma heurística dominante é sempre melhor que uma heurística dominada, pois é mais informada e, portanto, mais próxima do custo real.
Procura IDA*
IDA* é uma versão iterativa do A*, que evita o uso de memória para guardar os nós expandidos. A ideia é expandir os nós de forma semelhante ao A*, mas com um limite de profundidade. Se o limite for atingido, a procura recomeça com um limite maior, até encontrar o objetivo. IDA* é completo e ótimo se a função heurística for admissível e consistente.
- Completa: Sim, se h for admissível, b for finito e custo das acções >0
- Complexidade Temporal: \(O(b^m)\)
- Complexidade Espacial: \(O(bm)\)
- Ótima: Sim, se h for admissível, b for finito e custo das acções >0
Procura Melhor Primeiro Recursiva (RBFS)
Na sua essência, a RBFS implementa a procura melhor primeiro em espaço linear (através da recursão). Vamos procurando expandir sempre o nó, dentro dos filhos do nó atual, que tenha menor valor de f. Ao mesmo tempo, vamos sempre guardando recursivamente o melhor caminho alternativo ao nó atual - ou seja, o seu irmão ou antepassado com menor valor de f. Se nenhum dos seus filhos tiver f menor que esse valor alternativo, passamos então a explorar o nó alternativo guardado (a recursão permite-nos recuperá-lo). A procura termina assim que tentarmos expandir um nó que passa no teste objetivo.
- Completa: Sim, se a função heurística for admissível.
- Complexidade Espacial: \(O(bm)\)
- Ótima: Sim, se a função heurística for admissível.
- mauricio
10/09/2024