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

Home Fóruns Fórum Algoritmos Inteligentes de Busca com Python Divergência sobre a explicação do algoritmo de busca A*

Visualizando 2 posts - 1 até 2 (de 2 do total)
  • Autor
    Posts
  • #47544
    Bruno Andre Santos
    Participante

      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

       

      #47547
      Denny Ceccon
      Moderador

        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.

      Visualizando 2 posts - 1 até 2 (de 2 do total)
      • Você deve fazer login para responder a este tópico.