2

I'm implementing the A* algorithm using std::priority_queue on the openSet. At some point on the algorithm, as in wikipedia pseudo-code:

else if tentative_g_score < g_score[neighbor]
    tentative_is_better := true

followed by

if tentative_is_better = true
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

means that one has to perform a search on the priority_queue and change a value of one of their elements, which is not possible (as far as I understood).

Also, on this line:

if neighbor not in openset

one cannot search on a priority-queue and so this if cannot be implemented on a priority_queue, which I solved by creating a std::set which only tell us which elements are on the openSet (so that when I add/remove one element to the openSet, I add/remove to both std::set and std::priority_queue).

So, I wonder how can I avoid the first problem, or which std::container should one really use for this particular (yet general A*) implementation.

More generically, I wonder which is an efficient approach to A* using std containers?

Jorge Leitao
  • 19,085
  • 19
  • 85
  • 121

4 Answers4

2

I implemented A* algorithm with the STL before and got roughly through the same situation.

I ended up just working with std::vector only, using standard algorithms like push_heap and pop_heap (which are what priority_queue uses) to keep them in order.

To be clear: you should implement it with vectors and use algorithms to manipulate the vectors and keep them in a good state. It's far easier and potentially more efficient than using some alternatives to do it that way.

Update:

Today I would certainly try some of the Boost containers, like these ones: http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html But only if I'm allowed to use Boost (like for my own code for example).

Klaim
  • 67,274
  • 36
  • 133
  • 188
  • That is more a comment than an answer... xD – Jorge Leitao May 01 '12 at 07:02
  • 1
    No, I'm suggesting to ditch the priority queue or other containers and try to work only with vectors. It will be easier to work with and potentially more efficient. – Klaim May 01 '12 at 07:07
  • 1
    @J.C.Leitão: It's most of an answer. If it mentioned that the algorithms to use are `push_heap` and `pop_heap` (which are what `priority_queue` uses), then it would be complete. – Mike Seymour May 01 '12 at 07:08
  • Ok, but I've done that. I've already implemented with a vector... But the algorithm clearly "asks" for a priority_queue... that is why I'm asking here... – Jorge Leitao May 01 '12 at 07:10
  • @MikeSeymour Thanks, didnt remember what I used but I think it was those one, will add. – Klaim May 01 '12 at 07:13
  • @J.C.Leitão The algorithm is pseudo code, whatever the implementation only the logic suggested is necessary. Here priority_queue is just a shortcut for automatically sorting the vector but it forbid you to manipulate the vector directly so using the algorithms is the same without this problem. – Klaim May 01 '12 at 07:13
  • So you are suggesting that using a std::vector with the std::algorithms you mention is the same has using a priority_queue? (e.g. the O is the same?) – Jorge Leitao May 01 '12 at 07:20
  • 1
    While this type of approach will work it does change the asymptotic complexity of the algorithm - calling `std::make_heap` is at least an `O(n)` operation. A priority queue that supports `decrease/increase_key` will achieve `O(log(n))` updates, but unfortunately the `std::priority_queue` doesn't support these operations... – Darren Engwirda May 01 '12 at 07:33
  • priority_queue is only a wrapper class, by default over vector, see http://www.cplusplus.com/reference/stl/priority_queue/, also what Darren say. – Klaim May 01 '12 at 07:34
  • @MichalPrzybylowicz No it was console game code so no way you can ever see it. It was also years ago, I don't have access to it. You don't need to see specific code to understand how to use vector anyway. – Klaim Jan 31 '14 at 18:06
  • Today I would certainly try some of the Boost containers, like these ones: http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html But only if I'm allowed to use Boost (like for my own code for example). – Klaim Jan 31 '14 at 18:09
1

You can solve this by relying on the algorithm's behavior. Use a standard priority_queue, but instead of the increase/decrease_key operations, you insert a new node into the priority queue. Both successors now live in the priority queue. The one with the better priority will be taken first and then expanded and added to the closed list. When the additional node with higher priority is taken out it is already closed and thus discarded.

dornhege
  • 1,500
  • 8
  • 8
0

Unfortunately, the std:: containers don't currently support the operations you require - what's really needed is an "indexed" priority queue that supports decrease/increase_key style operations.

One option is to roll your own container (based on an augmented binary heap) that does this, if this sounds like too much work, you can almost fake it by making use of an augmented std::set data structure - both options are discussed in more detail here.

As others have said, another option is to just remove the priority queue entirely and try to maintain a sorted std::vector. This approach will work for sure, and might require the least coding on your part, but it does have significant implications for the asymptotic scaling of the overall algorithm - it will no longer be possible to achieve the fast O(log(n)) updates of the queue while maintaining sorted order.

Hope this helps.

Community
  • 1
  • 1
Darren Engwirda
  • 6,915
  • 4
  • 26
  • 42
  • Ok. Then, what if I use a priority queue with pointers together with a set of objects (ideally a unsorted set)? When I want to see if a node is on the openSet, I use the Set; when I need to retrieve the "best" node, I use pointers from the priority queue. I can ensure the set and the queue has the same number of elements, thus making the algorithm O(log(n)). Does this look reasonable?. – Jorge Leitao May 01 '12 at 18:05
  • If you're intending to use the `std::priority_queue` or the algorithms `std::make_heap, std::pop_heap` the problem you will face is how to implement an efficient update for the priority queue, when node scores change. Unfortunately the `std::` algorithms just don't support `decrease/increase_key`. I'm not sure how your suggested data structure overcomes this? – Darren Engwirda May 02 '12 at 02:31
  • What I've tried and worked is everytime I change a node's value, I push a temporary node with maximum value (so that it is on the top) and pop it back. For several simple examples with int pointers it worked: the queue was prioritized after each push/pop. I'm not sure this is valid everythime though, it shouldn't.. – Jorge Leitao May 02 '12 at 05:05
0

Without decrease_key, you can instead just re-add the node to the open set. Whenever you pop a node off the open set, check to see whether its key was greater than that node's current score; if so, continue without processing the node. That compromises the efficiency proof of A*, but in practice it isn't a serious issue.

Sneftel
  • 40,271
  • 12
  • 71
  • 104