以下是使用一个栈和一个大表格标记访问节点的深度优先搜索(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替换为优先级队列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中获取当前最小的节点，该节点可能不是节点N的兄弟节点，即它从包含节点N的当前子树“跳转”到另一个子树。这行代码的目的是什么？
有人能展示一下第二个算法的正确性吗，即为什么它可以用于IDA*算法？
更多信息更新：我已经花费了很多时间和精力研究这个问题，但由于以下原因，它似乎非常困难：
All graphs appear in the textbook are drawn tree-like, i.e. only one parent for each node, to show the concepts. This makes me confused: Does the second algorithm only work for trees?
Considering the line
if f((R, parent)) > LIMIT then do ...If the second one also works for graph, not just tree, then there might be many parents go to
R, should I consider all cases or just the current one,parent?
DFS2(N0, f, LIMIT)来实现迭代加深A*算法。 - VimNing