如何理解这种优先级队列深度优先搜索

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

我想解决的问题是对它的修改：它用PriorityQueuePQ替换堆栈S。该算法用于模拟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中获取当前最小的节点，该节点可能不是节点N的兄弟节点，即它从包含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永远不会低估达到目标状态的成本(。