Java 广度优先搜索 - 8 个滑块

Question

问题是这样的，广度优先搜索需要对一个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;

Answer 1

您在评论中提到您考虑了 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他的兄弟姐妹。

Java 广度优先搜索 - 8 个滑块

Java Breadth First Search - 8 Slider

java

algorithm

breadth-first-search