Java 广度优先搜索 - 8 个滑块
Java Breadth First Search - 8 Slider
问题是这样的,广度优先搜索需要对一个9值的棋盘数组进行排序。 1,2,3,4,5,6,7,8,0..按顺序,被告知不要修改大部分现有代码,在众多class个文件中添加BFS等语句。 运行 时间给出 1,2,5,3,4,8,6,7,0。它正确地移动了 0,但是关于路径,不确定要向现有代码添加什么来解决这个问题,以便路径和数字解析。
while (!frontier.isEmpty()) {
cur = frontier.remove();
if (cur.isGoal()) {
return cur;
} else if (cur.getDepth() < 15) {
visited.add(cur);
for (Node s : cur.expand()) {
if (!visited.contains(s)) {
s.setParent(cur);
s.setDepth(cur.getDepth() + 1);
frontier.add(s);
numNodesExplored++;
}
}
}
}
return null;
您在评论中提到您考虑了 1, 2, 3, 4, 5, 6, 7, 8, 0
这样的输出。这是方法 runBFS
做不到的。当您查看方法签名 Node runBFS(Node start)
时,您可以看到此方法 returns 是 Node
而不是节点列表。
除此之外,您还有一个逻辑错误。在下面的 code-block 中,您可以看到您将 Node s
他的 parent 添加到 s
。也就是说:s
是他自己的parent.
if (!explored.contains(s)) {
s.setParent(s); // here you add the wrong parent - it should be s.setParent(cur)
s.setDepth(cur.getDepth() + 1);
frontier.add(s);
numNodesExplored++;
}
只需将行更改为 s.setParent(cur)
。 cur
就是你要找的Node
他的兄弟姐妹。
问题是这样的,广度优先搜索需要对一个9值的棋盘数组进行排序。 1,2,3,4,5,6,7,8,0..按顺序,被告知不要修改大部分现有代码,在众多class个文件中添加BFS等语句。 运行 时间给出 1,2,5,3,4,8,6,7,0。它正确地移动了 0,但是关于路径,不确定要向现有代码添加什么来解决这个问题,以便路径和数字解析。
while (!frontier.isEmpty()) {
cur = frontier.remove();
if (cur.isGoal()) {
return cur;
} else if (cur.getDepth() < 15) {
visited.add(cur);
for (Node s : cur.expand()) {
if (!visited.contains(s)) {
s.setParent(cur);
s.setDepth(cur.getDepth() + 1);
frontier.add(s);
numNodesExplored++;
}
}
}
}
return null;
您在评论中提到您考虑了 1, 2, 3, 4, 5, 6, 7, 8, 0
这样的输出。这是方法 runBFS
做不到的。当您查看方法签名 Node runBFS(Node start)
时,您可以看到此方法 returns 是 Node
而不是节点列表。
除此之外,您还有一个逻辑错误。在下面的 code-block 中,您可以看到您将 Node s
他的 parent 添加到 s
。也就是说:s
是他自己的parent.
if (!explored.contains(s)) {
s.setParent(s); // here you add the wrong parent - it should be s.setParent(cur)
s.setDepth(cur.getDepth() + 1);
frontier.add(s);
numNodesExplored++;
}
只需将行更改为 s.setParent(cur)
。 cur
就是你要找的Node
他的兄弟姐妹。