我正在查看维基百科上的伪代码,并尝试使用它在 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);
}
}
最佳答案
我认为你可以通过 boolean maxDepth = false
来完成此任务实例变量。在 while 循环的每次迭代中,if maxDepth == true
然后退出,否则设置maxDepth = true
。在 dls
当您到达depth == 0
时然后设置maxDepth = maxDepth && children.isEmpty()
,即如果节点有任何子节点,则将 maxDepth 设置为 false。
此外,更改 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);
}
}
关于java - 关于java中迭代加深深度优先搜索的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16006008/