26

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

但我无法理解 BFS 和 DFS 算法。我最好的学习方法是把它画出来……我的画对吗？

在此处输入图像描述

在此处输入图像描述

谢谢！

4

2 回答 2

4

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

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

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

于 2013-05-31T00:22:05.840 回答
1

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

我之前在 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/

于 2013-05-30T18:11:45.507 回答