深度优先搜索和广度优先搜索理解-Java 学习之路

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

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

enter image description here

谢谢！

2 回答

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（先进先出），因此，在开始访问较低级别的节点之前，您将访问同一级别中的所有节点 .
回复于 2024-05-02T10:12:29+08:00
3

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

我已经看过了___20342_ . 如果你是为了好玩而做两个版本，一个带有DFS，另一个带有BFS，并对它们进行基准测试以观察差异 . 如果您想要追踪一些以便更好地理解，还可以从http://www.aispace.org/downloads.shtml下载图表搜索器和您认为有用的任何其他工具 . 最后但并非最不重要的是关于DFS和BFS的堆栈溢出问题http://www.stackoverflow.com/questions/687731/

回复于 2024-05-02T10:12:29+08:00

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

2 回答

相关问题