java - 关于java中迭代加深深度优先搜索的问题

Question

我正在维基百科上查看伪代码，并尝试用它来用 Java 编写算法。我的问题在于返回结果的方式不同。在维基百科上，返回了一个结果，这打破了搜索。在我的中，每次找到相关节点时，都会将其添加到列表中，并在处理完树后返回该列表。我将如何检测树的末端以便突破并返回列表？

维基百科:

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return null
}

我的:

    public List<String> dfid(Tree t, String goal)
    {
        List<String> results = new ArrayList<String>();
        String result;

        int depth = 0;
        while (true) //obviously not the way to go here
        {
            result = dls(t.root, goal, depth);
            if (result.contains(goal))
                results.add(result);
            depth += 1;
        }
        return results; //unreachable return
    }

    public String dls(Node node, String goal, int depth)
    {
        if (depth == 0 && node.data.contains(goal))
        {
            return node.data;
        }
        else if (depth > 0)
        {
            for(Node child : node.children)
            {
                dls(child, goal, depth-1);
            }
        }
        return null;
    }

编辑:修改后:

//depth first iterative deepening
        //control variables for these methods
        boolean maxDepth = false;
    List<String> results = new ArrayList<String>();

    public List<String> dfid(Tree t, String goal)
    {
        int depth = 0;

        while (!maxDepth)
        {
            maxDepth = true;
            dls(t.root, goal, depth);
            depth += 1;
        }
        return results;
    }

    public void dls(Node node, String goal, int depth)
    {
        if (depth == 0 && node.data.contains(goal))
        {
            //set maxDepth to false if the node has children
            maxDepth = maxDepth && children.isEmpty();
            results.add(node.data);
        }
        for(Node child : node.children)
        {
            dls(child, goal, depth-1);
        }
    }

Answer 1

我认为您可以使用 boolean maxDepth = false 实例变量来完成此操作。在 while 循环的每次迭代中，如果 maxDepth == true 则退出，否则设置 maxDepth = true。在 dls 中，当您到达 depth == 0 时，然后设置 maxDepth = maxDepth && children.isEmpty()，即如果节点设置 maxDepth 为 false有 child 。

此外，将 dls 更改为 void 方法。将 return node.data 替换为 results.add(node.data)，其中 results 是一个 ArrayList 或 HashSet 取决于你是否要过滤掉重复项。

如果你总是想访问树中的每一个节点，那么修改dls如下

public void dls(ArrayList<String> results, Node node, String goal)
{
    if (node.data.contains(goal))
    {
        results.add(node.data);
    }
    for(Node child : node.children)
    {
        dls(child, goal, depth-1);
    }
}