formulação correta do algoritmo A *
-
03-07-2019 - |
Pergunta
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?
Solução
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 .