STL priority_queue使用重新插入进行键减少不起作用-解网

问：

我正在尝试实现类似 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;
        }
};

c++ stl 优先级队列

你应该发布一个最小的可重现示例，其中只有最小的类，这些类不需要做任何事情或几乎什么都不做，然后用一小段代码来演示问题，使用一两个硬编码的例子来演示这个问题。我怀疑任何问题都与有关，因此您向我们展示的所有内容（除了类之外）都与实际问题无关。A*Compare

0赞 Ender_The_Xenocide 10/9/2023

@PaulMcKenzie 我删除了一些不相关的细节

0赞 Ender_The_Xenocide 10/9/2023

@273K开放是一个priority_queue，我包括了定义

0赞 PaulMcKenzie 10/9/2023

@Ender_The_Xenocide 从这个开始。将代码添加到您在那里看到的内容，直到您提到的问题出现。事实上，这正是你应该做的，以减少问题 - 从零开始，添加一些定义，然后进行测试。一旦你看到硬编码的，“我不在乎它是否与 A* 相关”的数据通过了测试，那么你就拿着代码并将其应用于更大的应用程序。

0赞 Ender_The_Xenocide 10/9/2023

@273K有错别字，就修复它

答：

-1赞 santranti 10/9/2023 #1

这是使用时的常见错误。修改元素的键并重新插入后，队列不会意识到此更改。这扰乱了优先级顺序。不幸的是，STL缺乏直接操作。因此，人们经常求助于重新插入技术来规避这一限制。std::priority_queuepriority_queuedecrease_key

为了使您的实现步入正轨，您可能需要修改以下几点：

处理重复项：我注意到您正在利用该集合来绕过已处理的节点，这很好。但是由于重新插入方法，队列最终可能会容纳同一节点的多个版本。这是一个棘手的情况，因为即使您首先以最准确的成本处理节点，冗余副本仍保留在队列中。closedopen
比较器调整：比较器必须区分具有相同 .打破这种联系的一个方便技巧是考虑另一个属性。fcost

这是我的建议：

1. 比较器修改

当节点共享相同的节点时，您可以使用启发式值（ value）来区分它们。通常，具有较小启发式的节点被赋予更高的优先级。fcosth

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;
}

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

编辑：

好的，在阅读了您的评论后，我决定为您的问题添加一些更适合您的部分。问题在于它没有针对频繁更新节点的数据结构进行优化。事实上，没有机制可以在重新插入后重新评估已修改项目在队列中的位置。这样做的问题是，如果以前具有更高优先级的其他节点仍在队列中，则新插入的更新节点并不能保证它将是顶部。std::priority_queue

您可以使用两种方法之一：

利用不同的数据结构

正如我之前所说，对于节点更新来说，这不是一个非常好的数据结构。因此，您可以使用替代项，例如 or 因为它们支持和操作。std::priority_queueboost::heap::fibonacci_heapboost::heap::d_ary_heapincreasedecrease

不过，如果你真的坚持使用，你可以尝试下一种方法：std::priority_queue

强制使用完全刷新进行优先级更新：

如果您仍打算使用，可以尝试通过重建整个队列来暴力破解正确的值。这是非常低效的，并且最终会因大量节点值而减慢速度。下面是一个片段作为示例：std::priority_queue

// Create a temporary container to hold nodes
std::vector<Node*> tempContainer;

while (!open.empty()) {
    tempContainer.push_back(open.top());
    open.pop();
}

// Re-insert nodes into the priority queue
for (Node* node : tempContainer) {
    open.push(node);
}

每次刷新节点的值时都可以这样做，但正如我所说，这种方法效率低下，并且可能会因大量节点值而减慢速度，但它保证了正确性。就我个人而言，我会尝试使用我之前提到的替代方案。

希望这能清楚。

STL priority_queue使用重新插入进行键减少不起作用

STL priority_queue using reinsertion for key decrease not working

评论

评论