我将俄罗斯方 block 作为一个有趣的副项目(不是家庭作业)，并希望实现人工智能，以便计算机可以自己玩。我听说这样做的方法是使用 BFS 搜索可用位置，然后创建最合理的放置位置的总分...
但我无法理解 BFS 和 DFS 算法。我学得最好的方法是画出来……我的画对吗？
谢谢!
最佳答案
您遍历的最终结果是正确的，您非常接近。但是，您在细节上有点偏离。
在深度优先搜索中，您将弹出一个节点，将其标记为已访问并堆叠其未访问的子节点。以该顺序。树的顺序可能看起来无关紧要，但如果你有一个带有循环的图，你可能会陷入无限循环，但这是另一个讨论。
给定算法的基线，在你将根节点压入堆栈后，你将开始你的第一次迭代，立即弹出 A。它不会留在堆栈上，直到算法结束。您将同时弹出 A、堆栈 D、C 和 B(或 B、C 和 D，您可以从左到右或从右到左进行，这是您的选择)并将 A 标记为已访问。现在，您的堆栈底部是 D，中间是 C，顶部是 B。
下一个弹出的节点是 B。您将 F 和 E 压入堆栈(我将保持与您相同的顺序)，将 B 标记为已访问。堆栈从上到下有 E F C D。接下来，弹出 E，不添加新节点，并将 E 标记为已访问。循环将继续，对 F、C 和 D 执行相同操作。最终顺序为 A B E F C D。
我将尝试以与您类似的方式重写算法:
Push root into stack
Loop until stack is empty
Pop node N on top of stack
Mark N as visited
For each children M of N
If M has not been visited (M.visited() == false)
Push M on top of stack
广度优先搜索我就不赘述了，算法完全一样。区别在于数据结构及其行为方式。队列是 FIFO(先进先出)的，因此，您将在访问较低级别的节点之前访问同一级别的所有节点。
关于java - 深度优先搜索和广度优先搜索理解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16842748/