Может ли Astar посещать узлы более одного раза?

Question

Я читал Astar vikipedia article. В своей реализации они проверяют каждый узел, если он находится в наборе closed, и если да, то они пропускают его. Разве не возможно, что если эвристика допустима, но NOT согласуется с тем, что нам может потребоваться повторно обратиться к узлу дважды (или более), чтобы улучшить его значение f? Это соответствующий код

for each neighbor in neighbor_nodes(current) 
    if neighbor in closedset //This if condition bothers me 
     continue 
    tentative_g_score := g_score[current] + dist_between(current,neighbor) 
    if neighbor not in openset or tentative_g_score < g_score[neighbor] 
     came_from[neighbor] := current 
     g_score[neighbor] := tentative_g_score 
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) 
     if neighbor not in openset 
      add neighbor to openset 

Answer 1

Ответ на ваш вопрос ниже psuedocode на связанной странице, а также в разделе Описание на этой странице. Из замечания ниже коды псевдо:

Примечания: выше псевдокод предполагает, что эвристический функция монотонные (или последовательные, см ниже), который является частым случаем во многих практических проблемах, таких как Кратчайшие Расстояние Путь в дороге сетей. Однако, если предположение неверно, узлы в закрытом наборе могут быть заново открыты и их стоимость улучшена. Другими словами, закрытый набор может быть опущен (с получением алгоритма поиска деревьев), если гарантируется существование решения или если алгоритм адаптирован так, что добавляет новые узлы в открытый набор, только если они имеют более низкую f , чем при любой предыдущей итерации.

Так что да, псевдокод предполагает, что эвристика является последовательной и ее необходимо будет изменить, если бы ее не было.