Вопросы об углублении глубины итерации Первый поиск в 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 
} 

Mine:

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; 
    } 

Edit: После изменений:

//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, если узел имеет детей.

Кроме того, смените dls на метод пустоты. Заменить 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); 
    } 
}