Can Astar visit nodes more than once?
a-star
Solution
The answer to your question is below the psuedocode on the linked page, and also in the Description section on that page. From the remark below the psuedo code:
Remark: the above pseudocode assumes that the heuristic function is monotonic (or consistent, see below), which is a frequent case in many practical problems, such as the Shortest Distance Path in road networks. However, if the assumption is not true, nodes in the closed set may be rediscovered and their cost improved. In other words, the closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower f value than at any previous iteration.
So yes, the pseudocode does assume the heuristic is consistent and would have to be modified if it was not.
Problem
I've been reading wikipedia's Astar article. In their implementaion, they check each node if it's in the `closed` set, and if so they skip it. Isn't it possible, that if the heuristic is admissible but NOT consistent, that we might need to revisit a node twice (or more) in order to improve it's `f` value? This is the relevant code ``` 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 ```