1
\$\begingroup\$

I'm trying to implement A*.

I'm storing the queue of nodes to visit in a min-heap, and I'm seeing the same node being added more than once to it (with different priority). Wikipedia's pseudocode suggests to avoid duplicates in the queue (if neighbor not in openSet), but:

  1. I'm not sure how to do that in a good way. I'm using a min-heap to store the queue, and there's no way to quickly search it to avoid duplicates.
  2. I'm not sure if I even need to bother, as it doesn't seem to affect correctness, but maybe I just didn't find the right testcase.

So is this problematic or not? Can I just keep the duplicates in the queue and not worry about it? Can this cause performance issues?


Wikipedia makes a remark about the duplicates. It suggests to eliminate them to avoid getting a suboptimal path at the end (and suggests a way to do so), but this sounds like nonsense to me, because the suboptimality can be trivially avoided, and their pseudocode already does so (before updating the 'parent node' of a node, they check if the new path is cheaper than the existing one (if tentative_gScore < gScore[neighbor] in their pseudocode), which already should be enough).


Here's an example scenario where I'm getting the duplicate.

I'm doing pathfinding on a grid, with 4-way movement, and the heuristic being manhattan distance to the goal (with ties broken by eucledian distance to the goal).

Let' say I'm in this situation:

enter image description here

The gray cells represent the min heap, with the number representing the estimated total cost to the goal.

In this state, the next cell to be processed is the one above 2. And that causes the cell above that one (currently having cost 28) to be added to the heap again with cost 26.

\$\endgroup\$
2
  • \$\begingroup\$ Hmm .. how come you have so many 26s and 28s that are obviously different distance from the goal? Also note that it's okay for nodes to have their "Estimate" improved (e.g. by finding a shorter alt route). Mandatory illustrative material - qiao.github.io/PathFinding.js/visual \$\endgroup\$
    – Kromster
    Commented May 2 at 6:53
  • \$\begingroup\$ @Kromster 26s and 28s are the total estimated distance (true distance from start to this point, plus estimated distance to the end; all of those being manhattan distance), so they look correct to me. "okay for nodes to have their "Estimate" improved" Mhm, but I think that works regardless of the duplicates in the queue (if, when inserting a better duplicate, you pop the existing element, you get the same end behavior). \$\endgroup\$ Commented May 2 at 7:02

2 Answers 2

2
\$\begingroup\$

I did some more tests, and:

  • When using an ordinary heuristic ("admissable" and "consistent", I think?), duplicates don't affect the end result, and just waste some computation time.

  • When using a greedy heuristic (which is neither), duplicates can result in a slightly more optimal path at the end (but the path is suboptimal either way with this heuristic), but at the cost of requiring more iterations.

So I ended up following @DMGregory's comment and adding a bool visited; to the Node structure. (Set to true when popping an element from the heap; if already true ignore this one and pop the next.)

I believe this is not entirely equivalent to deduplicating when inserting into the queue if your heuristic is not "consistent" (since theoretically you could have the same entry inserted into the queue more than once at different times), in this case it could make the resulting path suboptimal when it otherwise wouldn't be. But at least now I don't see this as a big problem, since usually I expect to be using a consistent heuristic.

\$\endgroup\$
0
\$\begingroup\$

If you can avoid reprocessing a node that you already processed (aka when you pull off a duplicate with a higher f) then it will work just fine.

Using this strategy each node will be added at most n times where n is the number of neighbors it has. In your example case that would be 4.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ To add onto this, to "avoid reprocessing a node that you already processed", you can add it to a "Closed" hash set and check for membership when you dequeue, or you can set a "visited flag" on the node data structure. I've seen some profiling that suggests allowing duplicates this way is faster in practice than doing an update-in-place if a node already in the frontier is reached via another path, but I haven't been able to recall the source to cite it here. \$\endgroup\$
    – DMGregory
    Commented May 2 at 11:52
  • \$\begingroup\$ To echo the above, I've always gone with some version of a closed flag on the node or maybe a parallel array of flags depending on the situation. In my cases it's been a fast, relatively low memory way to deal with it. \$\endgroup\$
    – Pikalek
    Commented May 2 at 14:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .