Incorrect implementation about python-astar HOT 5 CLOSED

Thanks for your input ! - I don't think i'm going to make any change anyway : The "heuristic cost" of a given node is not meant to change over time in a general case; so I don't see any improvement in reordering the heap for each visited node. Contrary to what you mean, this implementation is 100% correct, at least regarding this.
If you need to tweak it case-specific improvements, I recommand you to craft your own implementation -
Cheers,

from python-astar.

Let me explain. The heuristic value cannot change - correct. But the algorithm can find an alternate shorter path to a node X, which means the g-value needs to be updated. You are correctly updating it in this case, but merely updating the object does not re-sort the heap itself. The updated object should be brought up in priority, which is not done here.

Because of this, the line 87: current = heappop(openSet) no longer returns the element with lowest f-value. Still, the algorithm finds a solution, but that may be not the optimal one.

I assume you made the mistake by implementing the pseudo-code in python, but mistaken the heap object for auto-sorting priority queue.

from python-astar.

I understand your explanation, but you may have missed something in the definition of heappush/heappop : The heap is re-sorted, so heappop always returns the best item. (as illustrated here : https://docs.python.org/3/library/heapq.html#basic-examples) ( https://stackoverflow.com/questions/19979518/what-is-pythons-heapq-module ).

I'm sorry to insist, but heappush/heappop really actually do the auto-sorting thing, that's why these are made for

Anyway It would be very kind from you if you managed to provide a unit test that illustrates the issue

from python-astar.

Let me try once more. In lines 100-101, you modify the neighbor object in-place. This object may be already present in the heap, in which case, after the modification, the heap is not magically re-sorted, i.e., the heappop will not return this object even if it's the best (you can easily test this yourself).

from python-astar.

@jaromiru Thank you for insisting on your explanations, I've fixed the code, and will release it soon - It seems that I'm one of those guys who "understand quickly if explained for a long time" :)

from python-astar.