C ++ A-star implementation - determining whether a node is already in the priority queue of open positions

Question

One step of the A * search algorithm requires finding a list of open nodes for the node you are currently interacting with and adding node if it does not already exist, or updating its value and parent if it is present, but with a higher weighing more than the current version of node.

These behaviors are not supported in the STL priority_queue structure. How do I complete this step?

Updates since this question gets a lot of views:

• std :: priority_queue may seem like a good choice for this, but it is not.

• The A * implementation itself is a huge confidence enhancer, but after you have done this, you should try switching to the use provided by boost. I was nervous about the installation when I asked this question, but the installation is very simple and will not cause any complications; and A * is not the only useful functionality boost provides. (In particular, if you do not use your string processing functions, you will end up writing your own copy, I speak from personal experience ...)

Answer 1

You can use a simple vector or array to store items, and then use std::make_heap , std::push_heap , std::pop_heap , std::sort_heap , std::is_heap and std::is_heap_until to control it.

This allows you to break containment and implement custom operations in the priority queue without having to perform standard operations yourself.

Answer 2

STL priority_queue not suitable for implementing A *. You need a heap structure that supports the increase operation to change the priority of already inserted items. Use Boost.Heap to implement many classic heaps.

EDIT: The Boost.Graph library has an implementation of A * search .

Answer 3

If you are limited by STL, you can use the STL Set and permanently erase and reinsert items (with a new priority).

 Set< pair<int,int> > s; // < priority,value > s.insert( make_pair(0,5) ); // Decrease Key operation // s.erase( s.find( make_pair(0,5) ) ); s.insert( make_pair(1,5) ); 

The time complexity is still O (log N), but it will probably take more time for large sets.

Answer 4

Here is the solution I used for this if you really want to use std :: priority_queue:

When you need to update a node that is already in the priority queue, just insert a new node with the same state and new value and parent in the queue. A recently updated copy of this node will first exit the queue and be added to your visited set. To deal with older duplicates, make sure that any node exits the queue against your visited set before processing it. If it is in the visited set, then the path with the least cost through this node has already been seen, so just ignore it and process the next node.

Answer 5

There are three possible solutions:

• Track the list of nodes that are currently open, regardless of priority queue. Try to create a list of nodes in the same way as for closed nodes.

• Create a node map (by coordinate) in an open-closed state.

• Install the Boost library, which includes the A * boilerplate implementation (I think in <graph> ).