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

Я читал статью wikipedia Astar . В своей реализации они проверяют каждый node, если он установлен в closed, и если это так, они пропускают его. Разве не возможно, что если эвристика допустима, а НЕ согласована, нам может потребоваться дважды вернуться к node (или более), чтобы улучшить ее значение 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

Ответы

Ответ 1

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

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

Итак, псевдокод предполагает, что эвристика последовательна и должна быть изменена, если бы это было не так.