Busca em Árvore 3

No último post sobre busca em árvore, vimos a Busca de Custo Uniforme, também conhecido por Busca pelo Menor Custo.

Vamos considerar que temos um espaço de estados muito grande, o algoritmo irá encontrar a busca pelo menor caminho, ou seja, o custo total mais curto. Mas até que ele encontre o melhor caminho para o objetivo, vai levar muito tempo.

Então nós temos que dar mais informações para o algoritmo, conhecimento. O tipo de informação que é mais comumente usado em busca é uma estimativa da distância entre o nó inicial e o nó objetivo.

Busca pela melhor escolha

Quando falamos de busca com informação, a abordagem busca pela melhor escolha seleciona o nó para expansão com base em uma função de avaliação f(n).

“Tradicionalmente, o nó com a avaliação mais baixa é selecionado para expansão, porque a avaliação mede a distância até o objetivo.” (NORVIG et RUSSEL, 2004, pg. 95)

Há uma família inteira de Buscas pela melhor escolha, com funções de avaliação diferentes, tendo como elemento principal uma função heurística h(n).

formula1

Busca Gulosa pela Melhor Escolha

A busca gulosa pela melhor escolha tenta expandir o nó mais próxima ao objetivo, supondo que isso levará a uma solução rápida. (RUSSEL et NORVIG, 2004). Ele avalia os nós usando a função heurística: f(n) = h(n).

A* Search (A star Search)

Essa busca expande o nó com o menor valor da função f que é definida pela soma dos componentes g+h.

f = g+h

A função g do caminho é apenas o custo do caminho. Vimos isso no post sobre Resolução de Problemas.

g(path) = path cost

A função h de um caminho é igual a distância estimada do objetivo.

h(path) = estimated distance to the goal

astarsearch

Supondo que nós temos um caminho do estado inicial S até o estado X, o valor de f(X) é a soma de g e h.

Minimizar g ajuda a manter o caminho curto, e minimizar h ajuda a manter o foco em achar o objetivo. O resultado é uma estratégia de busca que é a melhor possível no sentido de encontrar o caminho mais curto enquanto expande o menor número de nós possíveis.

A* Search encontra o caminho de menor custo de acordo com a função h:

Se a função h de um estado for menor ou igual ao custo verdadeiro do caminho até o objetivo através deste estado.

h(s) <= true cost

Em outras palavras, h nunca pode superestimar a distância até o objetivo.

Nós também dizemos que h é otimista ou que h é uma admissível, significando que h é admissível para encontrar o caminho de menor custo.

Comentários

Postagens mais visitadas