c++ - 从 STL 优先队列中搜索/删除？

Question

我的任务是为涉及解决“8 谜题”的任务编写 A* 搜索算法。

该算法的步骤之一是:

Add all the extended paths to Q. If the descendant state is already in Q, keep only the shorter path to state in Q (where Q is a Priority Queue (PQ)).

因此，我需要 搜索PQ 如果存在相同的状态但路径较短。如果相同的状态已经存在但路径更长，我将需要 删除 这个状态来自 PQ .

我被指示使用 STL PQ，而不是我自己的实现。我已经设法使用下面的方法来实现其他类型的搜索来创建一个 Min PQ - 它可以按需要工作。

auto cmp = [](Puzzle* a, Puzzle* b) { 
    return a->getHCost() > b->getHCost();
};


std::priority_queue<Puzzle*, std::vector<Puzzle*>, decltype(cmp)> Q(cmp);           

我怎样才能扩展我的实现，以便......

我可以执行蛮力搜索 - 循环遍历 STL PQ 的每个元素？

我可以通过索引删除 STL PQ 中某处的元素吗？ - 如果合适，将元素“向上”洗牌。

Answer 1

您可以有一个名为 shortest[] 的辅助数组，其中 shortest[i] 是到状态 i 的最短已知路径。然后，每当您进入 PQ 顶部的状态为 x 的元素时，您检查 shortest[x] 是否确实是找到的最短的，并执行您想要的任何操作，否则从 PQ 顶部删除该元素。

但是，鉴于这些状态来自 8 个拼图，您必须想出一种有效的方法来为它们提供唯一的识别号，并能够有效地取回它。
在 O(1) 中可以同时做这两种事情。我不确定我是否应该破坏我的个人想法，因为这毕竟是一项任务，你应该接受这样的挑战。