深度优先搜索和广度优先搜索理解

Question

我正在将俄罗斯方块作为一个有趣的侧面项目(不是家庭作业),并希望实现AI,以便计算机可以自己玩.我听说这样做的方法是使用BFS搜索可用的位置,然后创建最合理的放置位置的总分...

但我无法理解BFS和DFS算法.我学得最好的方法是把它画出来......我的图纸是否正确？

---

谢谢!

Answer 1

你的遍历的最终结果是正确的，你已经非常接近了。然而，你在细节上有点偏离。

在深度优先搜索中，您将弹出一个节点，将其标记为已访问并堆叠其未访问的子节点。以该顺序。对于树来说，顺序可能看起来无关紧要，但如果你有一个带有循环的图，你可能会陷入无限循环，但这是另一个讨论。

给定算法的基线，在将根节点压入堆栈后，您将开始第一次迭代，立即弹出 A。直到算法结束它才会保留在堆栈上。您将一次性弹出 A、堆叠 D、C 和 B（或者 B、C 和 D，您可以从左到右或从右到左执行，这是您的选择）并将 A 标记为已访问。现在，你的堆栈中 D 在底部，C 在中间，B 在顶部。

下一个弹出的节点是 B。您将把 F 和 E 压入堆栈（我将保持顺序与您的相同），将 B 标记为已访问。堆栈从上到下依次为 EFC D。接下来，E 被弹出，不添加新节点，并且 E 被标记为已访问。循环将继续，对 F、C 和 D 执行相同的操作。最终顺序是 ABEFC 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（先进先出）的，因此，您将在开始访问较低级别的节点之前访问同一级别中的所有节点。