迭代延长伪代码遍历所有节点

Question

使用迭代延长深度优先方法遍历图中所有节点的算法、伪代码或实际代码是什么?

Answer 1

我先给出graph

的深度优先伪代码

DLS(node, goal, depth, visited) 
{
  if ( depth >= 0 ) 
    {
    if ( node == goal )
      return node
    visited.insert(node)
    for each child in expand(node)
      if (child is not in visited)
          DLS(child, goal, depth-1, visited)
  }
}

，迭代DLS为

IDDFS(start, goal)
{
  depth = 0
  while(no solution)
  {
    visited = [] // <-- Empty List
    solution = DLS(start, goal, depth,visited)
    depth = depth + 1
  }
  return solution
}

您总是可以通过使用访问列表移除图形循环来转换树中的图形。:)