使用重新插入来减少键的STL优先级队列不起作用

Question

我正在尝试实现类似 A* 的算法，但在使用 STL

priority_queue

容器实现密钥减少时遇到困难。当我减少键时，我试图将元素重新插入队列，但它们仍然不会在具有更高键的元素之前弹出。

这是主要的类似 A* 的循环，删除了不相关的细节：

while (!(open.empty() || (goalExp && switchToEA(firstTimeGoal, reopen)) )) {
        Node *nextParent = open.top();
        open.pop(); // Where the node gets popped
        if (closed.find(nextParent) != closed.end())
            continue;
        closed.insert(nextParent);
        nextParent->expand((*graph)[nextParent->getState()]);
        
        for (auto &i: nextParent->getAdjacent()) {
            T state = i.first;
            cost_t edgeCost = i.second;
            Node *child;
            if (state_to_node.find(state) != state_to_node.end()) {
                child = state_to_node[state];

                if (nextParent->getGCost() + edgeCost < child->getGCost()) {
                    child->setGCost(nextParent->getGCost() + edgeCost);
                    child->setFCost(child->getGCost() + (*h)(state));
                    child->setBack(nextParent);
                    open.push(child); // Key decrease
                } 
            } else {
                child = new Node(nextParent->getGCost() + edgeCost, nextParent->getGCost() + edgeCost + (*h)(state),
                                 state, nextParent);
                open.push(child); // New node insertion
                state_to_node[state] = child;
            }
        }
}

优先级队列定义：

std::priority_queue<Node *, std::vector<Node *>, typename Node::Compare> open;

比较器类：

class Compare {
    public:
        bool operator() (BaseNode * a,BaseNode * b) {
            return a->fcost > b->fcost;
        }

        bool operator() (const BaseNode& a, const BaseNode& b) {
            return a.fcost > b.fcost;
        }
};

Answer 1

这是使用

std::priority_queue

时的常见错误。一旦修改元素的键并重新插入它，队列就不会意识到此更改。这扰乱了优先顺序。不幸的是，STL 的

priority_queue

缺乏直接的

decrease_key

操作。因此，人们经常诉诸重新插入技术来规避这一限制。

为了使您的实施步入正轨，您可能需要修改以下几项内容：

1. 处理重复：我注意到您正在利用

   closed

   设置来绕过已处理的节点，这很好。但由于重新插入方法，

   open

   队列最终可能会容纳同一节点的多个版本。这是一个棘手的情况，因为即使您首先处理成本最准确的节点，冗余副本仍保留在队列中。

2. 比较器调整：比较器必须区分具有相同

   fcost

   的节点。打破这种平局的一个方便技巧是考虑另一个属性。

这是我的建议：

1。比较器修改

当节点共享相同的

fcost

时，您可以使用启发式值（

h

值）将它们分开。通常，启发式较小的节点会被赋予较高的优先级。

class Compare {
public:
    bool operator() (BaseNode* a, BaseNode* b) {
        if (a->fcost == b->fcost) {
            return a->hValue > b->hValue; // I'm assuming there's an hValue in your node
        }
        return a->fcost > b->fcost;
    }

    bool operator() (const BaseNode& a, const BaseNode& b) {
        if (a.fcost == b.fcost) {
            return a.hValue > b.hValue;
        }
        return a.fcost > b.fcost;
    }
};

2。节点更新检查

不要直接将节点扔回队列，而是考虑将其标记为已更新。稍后，当您要处理节点时，请检查它是否已更新。如果是这样，请将其弹出并重新插入。这可以稍微简化事情。

if (nextParent->getGCost() + edgeCost < child->getGCost()) {
    child->setGCost(nextParent->getGCost() + edgeCost);
    child->setFCost(child->getGCost() + (*h)(state));
    child->setBack(nextParent);
    child->updated = true;  // You'd need to add this attribute to your Node
} 

加工时：

Node *nextParent = open.top();
if (nextParent->updated) {
    open.pop();
    open.push(nextParent);
    continue;
}

希望这对您的问题有所帮助。快乐编码！