Estou trabalhando em uma implementação do algoritmo Anytime Dynamic A* conforme descrito aqui . Estou em ~50% do caminho através de uma implementação inicial básica, mas estou preso na seguinte linha:
No procedimento ComputePath, na linha 19 diz
se s′ não foi visitado antes então
Esta é a única linha que consigo encontrar mencionando "visitando" um nó. O que significa "visitado"? Preciso adicionar um visitedbooleano a cada nó, se sim, quando faço um nó visitado ou não visitado?
Tenho certeza de que não importa, mas estou escrevendo esta implementação em Java 21
Em algoritmos de busca de grafos, 'visitação' normalmente significa calcular propriedades para, filhos de, ou de outra forma avaliar algum nó. A pergunta que está sendo feita é: "Já olhei para isso antes?" Um pouco antes no artigo que você referenciou (na seção 2) diz:
Parece que os valores de
v(s),g(s), ebp(s)são todos garantidos para serem definidos pelo código após a linha 15, então eu marcariascomo 'visitado' ali e garantiria que todos os nós começassem como não visitados. Em termos de como marcar um nó como visitado, um booleano é provavelmente a maneira mais fácil de fazer isso, mas há muitas opções.No entanto:
De forma mais pragmática, parece-me que a única razão para verificar se um nó já foi visitado antes é garantir que os valores de
v(s),g(s)ebp(s)sejam todos inicializados com alguns valores iniciais, então, se você estiver representando seus estados como objetos, provavelmente poderá apenas definir esses valores no construtor e ignorar completamente o absurdo da "visitação".As duas únicas instruções if que verificam se um nó foi visitado apenas inicializam esses valores, então, desde que você os defina no construtor sempre que criar um novo estado, você poderá remover essas instruções if com segurança.