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

Question

我正在制作俄罗斯方块作为一个有趣的副业项目（不是作业），并希望实现 AI，让电脑自己玩。我听说可以使用 BFS 搜索可用位置，然后创建最合理下落位置的聚合分数来完成。但我对 BFS 和 DFS 算法有些困惑。我最好的学习方式是画出来...我的绘图正确吗？

谢谢！

- user3871

---

注意：由于可能性变得非常非常大，使用DFS并不是很高效或实时的，因此您可以使用BFS根据某些计算得出合理的移动。虽然在这里不太相关，但您可能想了解Minimax算法用于人工智能，因为它相对简单，并且演示了如何更快地减少可能性以得出移动（通常在井字棋中）。 - wazy

@wazy 这将取决于数据。如果图表每层的节点数比高度多，会怎样呢？ - Luiggi Mendoza

我不想说“取决于”，但这相当依赖于你是想“快速”找到解决方案（或者至少尝试着这样做，而不一定是最优的），还是想评估每种可能的解决方案/组合。 - wazy

@wazy，这取决于情况。如果您了解数据方面的知识，则可以为其应用最佳算法。如果您对此一无所知，那么BFS可能就足够了。此外，这还取决于实际问题的本质。 - Luiggi Mendoza

@Luiggi Mendoza，是的，我不能做出任何假设，因此我之前的评论。 - wazy

Answer 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（先进先出）的，因此您将在开始访问下一级别的节点之前访问同一级别的所有节点。

- Vitor De Mario

Answer 2

首先，我认为您的遍历似乎还不错（从快速概述来看）。我将在下面给您提供一些有用的链接。

我以前在YouTube上找到过一些不错的视频，但这里有一个（不是我见过的最好的），涵盖了 http://www.youtube.com/watch?v=eXaaYoTKBlE。如果您只是出于兴趣而做，请制作两个版本，一个使用DFS，一个使用BFS，并对它们进行基准测试以观察差异。此外，如果您想追踪一些内容以便更好地理解，请从http://www.aispace.org/downloads.shtml下载图形搜索器和其他任何您发现有用的工具。最后但并非最不重要的是，关于DFS和BFS的stackoverflow问题 http://www.stackoverflow.com/questions/687731/。

- wazy