Busca Gulosa e Local

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

Busca gulosa
* A busca gulosa pela melhor escolha procura expandir o nó mais próximo ao objetivo seguindo a intuição de que isso a levará mais rápido ao objetivo.
* A busca pela solução avalia os nós usando uma função heurística: f(n) = g(n).
* Os métodos de busca gulosa costumam ser eficientes na maioria dos casos; porém, no pior caso, podem nunca encontrar uma solução.
* A busca gulosa não é ótima e pode levar a uma solução com caminho mais longo quando um passo inicial do caminho mais curto tiver custo maior do que um passo do caminho mais longo.
Busca Local: * Em muitos problemas o caminho para a solução é irrelevante.
* Jogo das n-rainhas: o que importa é a configuração final e não a ordem em que as rainhas foram acrescentadas.
* Se o caminho para a solução não importa, podemos utilizar um algoritmo de busca local.
* Algoritmos de busca local operam sobre um único estado corrente, ao invés de vários caminhos.
* Em geral se movem apenas para os vizinhos desse estado.
Vantagens:
– Ocupam pouquíssima memória (normalmente constante).
– Podem encontrar soluções razoáveis em grandes ou infinitos espaços de estados
Exemplo - Algoritmo Hill Climbing
* É um algoritmo guloso – escolhe sempre o primeiro melhor vizinho para progredir na busca.
* Essa abordagem pode ter bons resultados em alguns problemas. Sendo capaz de progredir rapidamente para a solução problema.