Home › Fóruns › Fórum Algoritmos Inteligentes de Busca com Python › Divergência sobre a explicação do algoritmo de busca A*
- Este tópico contém 1 resposta, 2 vozes e foi atualizado pela última vez 3 semanas atrás por
Denny Ceccon.
- AutorPosts
- 21 de janeiro de 2025 às 14:24 #47544
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
- Este tópico foi modificado 3 semanas, 1 dia atrás por
Bruno Andre Santos.
22 de janeiro de 2025 às 09:58 #47547Olá 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.
- Este tópico foi modificado 3 semanas, 1 dia atrás por
- AutorPosts
- Você deve fazer login para responder a este tópico.