3

我正在将俄罗斯方块作为一个有趣的副项目（不是家庭作业），并希望实现人工智能，以便计算机可以自己玩。我听说这样做的方式是使用 BFS 搜索可用位置，然后创建最明智的放置位置的总分......

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

1) 将节点添加到 ArrayList

  • nodeList.add(n nodes)

2) 连接节点

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

  • 传入节点进行连接：ex: 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) 循环遍历节点队列，将visited加入队列

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

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

  • 虽然 Queue 不为空...您应该创建一个新节点并将其设置为等于 Queue 的已删除节点：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)，您应该更改孩子的已访问状态 =true然后将其添加到队列中，q.add(child)...但是您不是在做这一切while(!q.isEmpty())吗？那么，q如果您要添加它，什么时候会是空的？

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

谢谢

4

2 回答 2

3

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

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

q在这种情况下，您的循环将包括删除队列中的第一个节点A，并添加所有已连接A但尚未访问的节点。换句话说，您将遍历矩阵的线A并找到B，C并且D连接到A。对于它们中的每一个，如果visited()返回 false，您会将它们添加到q并标记为已访问。在这个过程中，q将有B、C和D，并且所有的A-D都将visited() 为真。

在下一次迭代中，第一个节点q将是B。您将使其出队并看到它已连接到A和。由于调用时返回，因此您不会将其添加到. 并将被添加并标记为已访问。EFAtruevisited()qEF

如果继续，您将出队C,和D，而不向 中添加任何内容，因为所有节点都已被访问过。之后，将返回并且您的循环结束。EFqq.isEmpty()true

于 2013-05-29T21:06:04.180 回答
1

队列是您的待办事项列表。它是接下来要处理的节点列表。

当您在树/图的叶子处用完要处理的孩子时，队列将变为空。

于 2013-05-29T21:10:33.393 回答