7

Olá pessoal alguem consegue responder esta pergunta estou na duvida.

é admissível a heurística h(n)=0 para algorítimo A*

1

2 Respostas 2

7

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ó objetivo

O 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.

3

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.

5
  • 2
    Seria uma boa adicionar uma explicação para o algoritimo A* e a l a heurística h(n)=0 22/09/2017 às 11:26
  • 1
    @LeonanCarvalho, de total acordo, mas no momento eu preferi uma resposta rápida para que o AP esteja com a dúvida sanada. Não sei quando vou conseguir tratar disso com mais carinho. Se você postar uma resposta mais completa, me avise pois estou ansioso por isso 22/09/2017 às 11:29
  • 1
    Eu não tenho muito conhecimento sobre o assunto para fazer uma resposta canônica, mas eu gostei da sua resposta, foi à algura da pergunta. Deixei meu apoio tanto para pergunta como para resposta (+1) 22/09/2017 às 11:49
  • 1
    Foi a mesma coisa que pensei @Jefferson Quesado , pensei que estava pensando errado. 28/09/2017 às 23:15
  • @LeonanCarvalho, creio que a [futura] resposta desta pergunta consiga explicar o que é o A* 8/11/2017 às 13:28

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .