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

algorithm java breadth-first-search depth-first-search

2022-09-01 17:50:11

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

但是我在理解BFS和DFS算法时遇到了麻烦。我学习最好的方式是把它画出来...我的图纸是否正确？

enter image description here

谢谢！

答案 1

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

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

给定算法的基线，在将根节点推送到堆栈中后，您将开始第一次迭代，立即弹出 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（先进先出），因此，在开始访问下级节点之前，您将访问同一级别中的所有节点。

答案 2

首先，我相信你的遍历似乎没问题（从快速概述）。我将在下面给你一些有用的链接。

我以前在youtube上发现了一些关于此的体面视频，但这里有一个（不是我见过的最好的）涵盖了它 http://www.youtube.com/watch?v=eXaaYoTKBlE。如果你这样做是为了好玩，请制作两个版本，一个使用DFS，另一个使用BFS，并对它们进行基准测试以观察差异。如果您想跟踪一些工具，也可以从 http://www.aispace.org/downloads.shtml 下载图表搜索器和您认为有用的任何其他工具，以便更好地理解。最后但并非最不重要的一点是，关于DFS和BFS的堆栈溢出问题 http://www.stackoverflow.com/questions/687731/