formulação correta do algoritmo A *

Question

Eu estou olhando para as definições do algoritmo A *-encontrar caminho, e parece ser definido um pouco diferente em lugares diferentes.

A diferença está na ação executada quando a atravessar os sucessores de um nó, e descobrir que um sucessor está na lista fechada.

• Uma abordagem (sugerida por Wikipedia , e este artigo ) diz: se o sucessor está na lista fechada, simplesmente ignorá-lo
• Outra abordagem (sugerida aqui e aqui , por exemplo) diz: se o sucessor está na lista fechada, examinar o seu custo. Se for maior do que a pontuação atualmente computada, remova o item da lista fechada para exame futuro.

Estou confuso - qual método é o correto? Intuitivamente, o primeiro faz mais sentido para mim, mas eu me pergunto sobre a diferença de definição. É uma das errado definições, ou são de alguma forma isomórfica?

Answer 1

A primeira abordagem é ideal somente se o caminho ideal para qualquer Estado repetido é sempre o primeiro a ser seguido. Esta propriedade é válida se a função heurística tem a propriedade de consistência (também chamado monoticity ). A função heurística é consistente se, para cada n nó e cada n' sucessor de n, o custo estimado de alcançar a meta de n não é maior do que o custo passo de chegar ao n' de n mais o custo estimado de alcançar a meta de n .

A segunda abordagem é ideal se a função heurística é meramente admissível, que é, nunca superestima o custo para atingir a meta.

Cada função heurística consistente também é admissível. Embora a consistência é uma exigência mais rigorosa do que a admissibilidade, um tem que trabalhar muito duro para inventar funções heurísticas que são admissíveis, mas não consistente.

Assim, embora a segunda abordagem é mais geral, uma vez que trabalha com um subconjunto estritamente maior de funções heurísticos, a primeira abordagem é geralmente suficiente na prática.

Referência: a subseção A * pesquisa: minimizando o total estimado de custos solução na seção 4.1 Informado (heurística) Pesquisa Estratégias do livro Inteligência Artificial: A Abordagem moderna .