Divergência sobre a explicação do algoritmo de busca A*

[Bruno Andre Santos]

Olá!

A explicação do algoritmo A* apresentada no vídeo se difere do algoritmo A* apresentado no livro de Inteligência Artificial (Norvig e Russel) e também da explicação sobre a operação do algoritmo na Wikipedia

De acordo com o livro de IA e o site da Wikipedia, o custo estimado da solução (função f(n), mostrada na imagem abaixo) para cada nó é calculado usando o somatório das distâncias do nó inicial  até o nó atual (g(n)) mais a função heurística (h(n)). Por exemplo, no instante 9m04s do vídeo (Busca A* – teoria (Busca com informação)), a soma seria 87 + 57 + 139 = 283 (custo de Porto União -> São Mateus -> Irati), em vez de 57 + 139 = 196, conforme mostrado no vídeo.

Print da Wikipedia:

Gostaria de saber, por gentileza, por qual motivo vocês usaram um método diferente para o custo estimado da solução.

Em outras palavras, a função g(n) que vocês usaram não está levando em consideração o custo do caminho do nó inicial até n (vocês estão usando a distância entre o penúltimo e último nó).

Obrigado

 

• This topic was modified 1 year, 4 months ago by Bruno Andre Santos.

[Denny Ceccon]

Olá Bruno,

Você tem razão, o professor fez uma simplificação considerando que a próxima cidade é definida a cada iteração do algoritmo, mas para definir o melhor caminho inteiro, o custo total deve ser considerado.

[Author]

Posts