Olá pessoal alguem consegue responder esta pergunta estou na duvida.
é admissível a heurística h(n)=0 para algorítimo A*
Se você se lembra do princípio básico do algoritmo A*, ele decide o próximo nó de um grafo a "perseguir" com base em uma função de avaliação f(n)
dada por:
f(n) = g(n) + h(n)
Onde:
g(n)
= custo até o momento para alcançar o nó n
(isto é, o nó atual)h(n)
= custo estimado para alcançar do nó n
(atual) até o nó objetivoO valor de h(n)
se chama heurística justamente porque é uma estimativa inteligente. Primeiramente, é uma estimativa porque se eu tivesse o valor real eu não precisaria fazer a busca pois já teria a resposta. Além disso, calcular o valor real é, de fato, fazer a busca. Então, o melhor que se tem a fazer é estimar da melhor forma possível.
Essas estimativas costumam ser simples e fáceis de calcular, e é isso que justamente torna esse algoritmo tão interessante. Num jogo, por exemplo, em que um personagem precisa localizar um alvo sob uma grade discreta (em que cada casa da grade é um nó do grafo), o valor de g(n)
é simplesmente a contagem de casas da grade da posição inicial do personagem até a casa atual n
(ou um valor muito alto caso exista ali um obstáculo). Uma boa heurística h(n)
é a distância, em unidades do espaço do mundo (supondo que a grade está construída nessa mesma unidade), entre o nó atual n
e o nó de destino (onde está o alvo).
Dizer que uma heurística é admissível é dizer que ela não superestima o custo real em todos os nós do grafo. Afinal seria um problema enorme se ela superestimasse (isto é, errasse pra mais do que o valor real), pois a busca poderia ser desviada de um caminho ótimo. No exemplo anterior, a grade é discreta, de forma que o personagem vai ter que andar sempre de uma casa a outra. Se ele andar em linha reta, ele vai andar 1 unidade do espaço, mas se ele andar na diagonal vai andar um pouco mais do que isso (Pitágoras explica!). Logo, usar unidades de distância é uma estimativa próxima do real (isto é, do número de casas que faltam ser andadas), mas que sempre vai errar pra baixo.
Assim, numa implementação correta do A* a heurística h(n)
só deve ser igual a 0 no nó objetivo. Se ela for 0 sempre, isto é, para todos os nós n
, será o mesmo que não usar heurística alguma e fazer a sua função de avaliação ser:
f(n) = g(n) + h(n) = g(n) + 0 = g(n)
Funciona? Sim, mas aí a busca é apenas baseada no custo, sem usar qualquer estimativa de caminho (que é a grande diferença do A*, permitindo encontrar um resultado ótimo se ele existir). Aliás, o algoritmo que se baseia somente no custo existe, e se chama Busca de Custo Uniforme.
Sobre a heurística, se você colocar h(n) = 0
, isso implica que não haverá uma busca guiada. Sem a heurística, não há otimizações de busca.
Então, sim, é plausível você por a heurística retornando um valor constante, mas isso fará com que a busca rápida e poderosa do A*
se torne lenta e fraca.