Error in A* implementation

[gdalle]

In the implementation of the A* algorithm, there is a vector called closed_set which is used to indicate whether a vertex has already been expanded.

Judging by the similar notations, this implementation is taken almost as-is from the Wikipedia page, but on Wikipedia the closed_set does not exist. In fact, the article clearly states that

When the heuristic being used is admissible but not consistent, it is possible for a node to be expanded by A* many times, an exponential number of times in the worst case.

Therefore, I think the presence of closed_set in the code is a mistake and should be corrected.

[gdalle]

@matbesancon @etiennedeg

[matbesancon]

if a vertex is expanded several times, are the following ones redundant with the first time this vertex is encountered? From your message I assume not

[gdalle]

Probably not, because this means we have found a cheaper path to said vertex, which may reveal a cheaper path to its neighbors

[matbesancon]

I'm ok with removing this. Even better if there is an example that fails to add to the tests

[captchanjack]

Hello! Just looking into this as well

Looks like the Wikipedia page you referenced used to have the closed_set documented in its algorithm, found a reference to an older version of the page

Pretty much all the implementations I've found online use a closed_set, e.g. another julia package, python, c++, even this youtube video

According to this source and this, both may be correct:

The first approach (i.e. one with closed_set) is optimal only if the optimal path to any repeated state is always the first to be followed. This property holds if the heuristic function has the property of consistency (also called monoticity). A heuristic function is consistent if, for every node n and every successor n' of n, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' from n plus the estimated cost of reaching the goal from n.

[gdalle]

Thanks for your input! Indeed, it looks like the closed set is useful to preserve optimality in cases where the heuristic is admissible but not consistent. See the following screenshots from Artificial Intelligence, a Modern Approach

[gdalle]

I left the closed_set in #125, let's close this for now