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

Question

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

但我很难理解算法。到目前为止，我的理解是：

1）向ArrayList添加节点

null

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;

• 创建新队列:queue q=new LinkedList（）；
• 将rootNode添加到队列:q.add(rootNode)
• 将访问标志设置为true:rootnode.visited（true）

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

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

null

谢谢

Answer 1

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

以您的图像为例，您将仅用节点A开始q。您将A标记为已访问。你就是这样开始的。

您的循环将包括删除队列q中的第一个节点，在本例中是A，并添加连接到A但尚未访问的所有节点。换句话说，您将遍历矩阵的一行A，并发现B、C和D连接到A。对于其中的每一个，如果visited()返回false，则将它们添加到q并标记为visited。在此传递中，q将具有b、c和d，并且所有a-d都将访问（）为true。