java - 俄罗斯方 block AI - 理解广度优先搜索的问题

Question

我将制作俄罗斯方 block 作为一个有趣的副业(不是家庭作业)，并希望实现 AI，以便计算机可以自己玩游戏。我听说这样做的方法是使用 BFS 搜索可用位置，然后创建最明智的放置位置的总分...

但我无法理解该算法。到目前为止，我的理解方式是:

1) 添加节点到ArrayList

• nodeList.add(n 个节点)

2)连接节点

• 使用邻接矩阵:adjMatrix[sizeOfNodeList][sizeOfNodeList]

• 传入要连接的节点:例如:connectNode(nodeA, nodeB);，它调用:connectNode(Node from, Node to):

  int fromNode=nodesList.indexOf(from);
  int toNode=nodesList.indexOf(to);
  
  //connect node A to B and B to A, set that i,j position = 1
  adjMatrix[fromNode][toNode]=1;
  adjMatrix[toNode][fromNode]=1;
  

在邻接矩阵中节点已经连接后...

3) 循环遍历节点Queue，将visited加入queue

• 创建一个新队列:Queue q = new LinkedList();
• 将 rootNode 添加到队列:q.add(rootNode)
• 将已访问标志设置为真:rootNode.visited(true)

这是我不明白的部分......

• 当队列不为空时...您应该创建一个新节点并将其设置为等于队列中已删除的节点:Node n = (Node)q.remove()<

但是如果你向它添加节点 q.add(rootNode) 和 q.add(child)，它什么时候会是空的？

• 接下来，检查 while child node = an unvisited child node and is not null，while((child=getUnvisitedChildNode(n))!=null)，你应该改变 child 的访问状态= true 然后将它添加到队列中，q.add(child)...但是你不是在做这一切吗 while(!q.isEmpty( ))？那么，如果要向 q 添加内容，它何时会为空？

我的队列 q 的目的是什么？是结果队列吗？

谢谢

Answer 1

您的队列 q 包含您尚未访问的节点。您应该只将尚未访问过的 q 节点添加到您的队列中。这样它将变为空，您已经探索过的节点将不会重新进入列表。

以您的图像为例，您将仅从节点A 开始q。您会将 A 标记为已访问。这就是您开始的方式。

您的循环将包括删除队列 q 中的第一个节点，在本例中为 A，然后添加连接到 A 的所有节点 并且还没有被访问过。换句话说，您将遍历 A 的矩阵线并找到 B、C 和 D 连接到 A。对于它们中的每一个，如果 visited() 返回 false，您将把它们添加到 q 并标记为已访问。在这一遍中，q 将有 B、C 和 D，以及所有 A-D 将 visited() 设为 true。

在下一次迭代中，q 上的第一个节点将是B。您将它出列并看到它连接到 A、E 和 F。由于 A 在您调用 visited() 时返回 true，因此您不会将其添加到 q。 E 和 F 将被添加并标记为已访问。

如果你继续，你将出列C、D、E和F，而不添加任何东西到q，因为所有的节点都已经被访问过了。之后，q.isEmpty() 将返回 true 并且您的循环结束。