2

我正在以编程方式解决 Boggle 游戏，并注意到深度优先搜索可用于查找板上所有有效的字母组合。此处描述了一个 Boggle 板。

假设我们有一个 4x4 板。对于板上的每个字符，使用 DFS 查找板上的所有路径（唯一的规则是您不能多次使用单个字符）。当 Boggle 板不是真正的图表时，为什么 DFS 会为此工作？此外，DFS 还可以应用于哪些其他类型的问题与此用法类似？

4

2 回答 2

0

您可以应用 DFS 或其他图形算法，因为您基本上也使用对角线的网格图。

在此处输入图像描述

把你的字母代替点，你就有了你的图表。现在为什么 DFS 会在这里工作？

当你在这个游戏中创建一个单词时——你连接了相邻的顶点，从而在图上创建了一条路径。因此，这是一种您可以开始（并改进）的方法。

  1. 创建一组英文字母表中的所有单词和一个合理的单词长度（假设单词不长于N字符）
  2. 从顶点开始迭代，并从每个顶点调用 DFS，直到 length N。对于每个单词（在规则中大于 3）检查它是否在字典中，如果是 - 将它们保存在某个地方。

你可以看到，在我的图表部分你可以很容易地找到这个词TORUS。

为什么使用 DFS 而不是 BFS 有意义？有几个原因：

  • 更容易实施
  • 空间复杂度更小

我的算法的复杂性是多少 假设您有一个网格n * m并且最长的单词有一个 length d。因为在我的算法中，您从所有顶点实现 DFS，并且 DFS 的复杂度为 O(b^d)，其中平均分支略小于 8（可能甚至小于 7，因为这里不能有循环）。在集合 id O(1) 中的搜索。所以复杂度是m * n * 8^d。

你怎么能改进它？尝试搜索这个词没有什么意义，TLRSOU因为英文字母表中没有以 . 开头的词TLR。所以一个更好的想法是将单词存储在一个trie中并快速终止没有意义的分支。

于 2015-12-18T03:05:44.753 回答
0

那是因为它是（或可以）由图形表示。Boggle 单词是由水平、垂直或对角线的相邻字母组成的。因此，您可以按照此规则制作字母之间的连接图。此外，DFS 不会两次访问一个节点，因为它保留了一个已经访问过的节点列表。所以它满足另一个规则，一个字母只能使用一次。

DFS（也包括 BFS）最终会发现图中的每条路径，因此您可以将生成的路径列表与有效单词字典进行比较，以确定单个 Boggle 板上的有效单词总数。

DFS 最著名的用途当然是寻路——几乎任何空间都可以映射到一个图中，然后找到最短或最长的路径。DFS 可以很好地找到图形的半径，从而找到最中心的节点。这对于像洪水填充算法这样的事情很有用，您希望快速填充不规则形状的内部，因为从图形的中心开始时边缘扩展会发生得最快。

于 2015-12-18T03:07:01.757 回答