0

I had a c++ implementation of the A* algorithm and I was using vectors as the data structures in which I stored open nodes. I was sorting the vector after every addition of a new node. That was too inefficient and I was told to start using priority queue to avoid sorting.

The problem I have with priority queue is that if I find a better path to a node that's already in the openNodes queue, I need to update its F value. The nodes in the queue are sorted by the F value, but when I update it, the node's position in the queue doesn't change. This means that I can end up with a sub-optimal path.

I tried to fix this issue by doing the following pattern whenever I would change the value of a node that's in the openNodes queue:

1) Update the F value of the node.

2) In the priority queue, pop and temporarily store all values that are before the node I'm looking for. Pop and store that node as well.

3) Loop through the temporary vector of nodes and push them back into the priority queue.

 //...updated the F value of a node
 std::vector<Node*> temp;
 //the loop condition checks if the current node on top of the queue is the node I'm updating
 while (openNodes.top()->getId() != (*neighbours)[i]->getId()) {    
    temp.push_back(openNodes.top());
    openNodes.pop();
 }
 temp.push_back(openNodes.top());
 openNodes.pop();
 for (int k = 0; k < temp.size(); k++) {
    openNodes.push(temp[k]);
 }

This approach does solve the problem of finding a sub-optimal path, but just like in the beginning, it's too inefficient. Is there a better way of solving this? Should I even use priority queue at all?

Peacetoletov
  • 23
  • 3

1 Answers1

-1

I don't really understand your code example, but for me it sounds like you should do the following:

  1. Get the node your are updating.

  2. Calculate the new F value.

  3. Did it change? Nope? Than you are done.

  4. Oh! It did change? Then pop this node from the queue. (Popping the node should not change the fact that your queue is already sorted.)

  5. Walk through the whole queue looking where the updated node belongs.

  6. Insert the updated node at the right place. The queue stays sorted.

In case you are not seeing it here, what you need is insertion sort!

jan.sende
  • 750
  • 6
  • 23
  • I'm pretty much doing what you're saying, except for 4: As far as I'm aware, I can only get the top element of the queue. Therefore, to be able to pop the node, I need to pop all the nodes before that one. That's what I'm doing in the posted code. Popping all the nodes that are "in the way", storing them, and then pushing them back in. – Peacetoletov Jul 27 '18 at 15:47
  • The fact that you need access - _modifying_ access, no less - to items other than the "highest" suggests that you should probably not be using `priority_queue` at all... I think I would just use a `vector` and then do either `partial_sort` or `nth_element` to ensure the first element the top one. – ravnsgaard Jul 27 '18 at 15:54
  • @ravnsgaard Yeah, that makes sense, thank you! Do you think I could also use insertion sort, as jan.sende suggests? I looked it up and I think it could fit the task I'm trying to solve well. – Peacetoletov Jul 27 '18 at 15:58
  • Ah yes! @ravnsgaard is right. I thought you were talking about a custom queue. If you are using the standard library one, you are indeed using the wrong container type! – jan.sende Jul 27 '18 at 15:59