如何理解这个优先队列深度优先搜索？

Question

以下是用一个堆栈和一个大表来标记访问节点的伪代码实现深度优先搜索（DFS）：

DFS(N0):
   StackInit(S)
   S.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   S.push((null, N0))
   while !isEmpty(S) then do
      (N, parent) := S.pop()
      R := next((N, parent))
      if isNull(R) then do
         continue             // So no new node add to this layer.
      S.push((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do    // If it's goal don't have to explore it.
         return true
      markVisited(R)
      if depthMax((R, parent)) then do
         continue
      S.push((null, R))
   return false

我想解决的问题是对它的修改：它S用 PriorityQueue替换堆栈PQ。该算法用于模拟 IDA* 算法（这在教科书中有说明，不幸的是不是用英文写的，所以我不会提供参考/书名）：

---

DFS2(N0, f, LIMIT):
   PriorityQueueInit(PQ)
   // A node (N, parent) stored in PQ represents a path from `N0` to `N`\
        passing the node `parent`; A node with smaller value on f() is \
        prioritized than those with larger value.
   PQ.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   PQ.push((null, N0))
   while !isEmpty(PQ) then do     // (1)
      (N, parent) := PQ.poll()
      R := next((N, parent))      // (2)
      if isNull(R) then do
         continue
      PQ.offer((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do
         return true
      markVisited(R)
      if f((R, parent)) > LIMIT then do
         continue
      PQ.offer((null, R))
   return false

• (1)：在A*算法中，优先级队列用于存储未被探索的节点，即开放列表。虽然在我提供的第一个 DFS 伪代码中，堆栈S是关闭列表，所以我假设在第二个伪代码中PQ也是关闭列表。那么第二个伪代码如何模拟 IDA* 算法，有一个关闭列表呢？
• (2)：它从 中获取当前最小的节点PQ，它可能不是 node 的兄弟节点N，即它从当前子树 contains跳转到另一个子树N。这条线的目的是什么？

谁能告诉我第二种算法的正确性，即为什么它可以用于 IDA* 算法？

---

更新了更多信息：我在这个问题上花了很多时间和精力，但似乎很难，因为以下几点：

1. 教科书中出现的所有图形都是树状绘制的，即每个节点只有一个父节点，以显示概念。这让我很困惑：第二种算法是否只适用于树？

2. 考虑到线路

   if f((R, parent)) > LIMIT then do ...
   

   如果第二个也适用于图，而不仅仅是树，那么可能会有很多父母去R，我应该考虑所有情况还是只考虑当前情况，parent？

Answer 1

这里发生了很多事情。

据我所知，这段代码总是返回到达队列顶部的第一个目标节点。在以下关于 f 和 next 的假设下，该目标节点是 f 最优的。但我不会称之为 IDA*。

首先，通常 A* 和 IDA* 都会同时打开当前节点的所有邻居。这段代码...没有。它使用迭代器，但只有一个循环。第一次推送是针对当前节点的下一个兄弟节点，第二次推送是针对子节点。我想这很好，除了兄弟姐妹应该以递增的 f 阶进行枚举，这样一个有前途的兄弟姐妹就不会在一个没有前途的兄弟姐妹之后被隐藏。

其次，与 A* 不同，IDA* 没有封闭列表。从某种意义上说，IDA* 总是有一个搜索树，因为如果它到达两个等效节点，它仍然将它们视为不同的节点。A* 确实有一个关闭列表，但它比此处提供的更复杂。A* 处理循环的方式是，如果它发现到已经关闭的节点的更便宜的路径，那么它会重新打开该节点。这段代码没有，所以只有在不需要重新打开节点的情况下它才是正确的。因此，这段代码需要 f 成为所谓的一致启发式（在每条路径上，当您遵循该路径时，f 永远不会下降），而 A* 只需要 f 是可接受的（f 永远不会低估达到目标的成本状态）。