功能广度优先搜索

4 回答

• 5

  您必须跟踪您访问的节点 . 列表在ML家族中不是王者，他们只是寡头之一 . 您应该只使用一组（基于树）来跟踪访问过的节点 . 与变异节点状态相比，这将添加一个对数因子，但是它更加清晰，这并不好笑 . 如果您对节点有了更多了解，可以使用不基于树的集合（比特矢量说）来消除日志因子 .

  回复于 2024-05-02T15:57:09+08:00
• 46

  一种选择是使用 inductive graphs ，它是表示和使用任意图形结构的功能方式 . 它们由Haskell的 fgl 库提供，并由Martin Erwig在"Inductive Graphs and Funtional Graph Algorithms"中描述 .

  如需更温和的介绍（带插图！），请参阅我的博客文章Generating Mazes with Inductive Graphs .

  归纳图的技巧是他们让你 pattern match on graphs . 使用列表的常用功能习惯是将它们分解为头元素和列表的其余部分，然后对其进行递归：

  map f []     = []
  map f (x:xs) = f x : map f xs
  

  归纳图让你做同样的事情，但对于图表 . 您可以将归纳图分解为节点，边缘和图形的其余部分 .

  pattern matching on a node http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/match1.png

  这里我们匹配节点 1 及其所有边缘（以蓝色突出显示），与图表的其余部分分开 .

  这让我们可以为图形编写一个 map （在Haskellish伪代码中可以用模式同义词实现）：

  gmap f Empty                     = Empty
  gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest
  

  与列表相反，这种方法的主要缺点是图形没有一种自然的分解方法：可以通过多种方式构建相同的图形 . 上面的 Map 代码将访问所有顶点，但是以任意（依赖于实现）的顺序 .

  为了解决这个问题，我们添加了另一个构造：一个带有特定节点的 match 函数 . 如果该节点在我们的图表中，我们就像上面一样获得成功的匹配;如果不是，则整场比赛失败 .

  这个结构就足以编写一个DFS或BFS-优雅的代码看起来几乎完全相同！

  我们只是手动将节点标记为已访问，而只是递归到图表的其余部分，除了我们使用原始图形的较小和较小部分处理的节点 . 如果我们尝试访问我们已经看到过 match 的节点，它将不在剩余的图中，并且该分支将失败 . 这使得我们的图形处理代码看起来就像我们在列表上的正常递归函数一样 .

  这是这种图的DFS . 它使节点堆栈作为列表（前沿）访问，并开始初始边界 . 输出是按顺序遍历的节点列表 . （如果没有一些自定义模式同义词，这里的确切代码不能直接用库编写 . ）

  dfs _frontier Empty = []
  dfs [] _graph = []
  dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
    dfs (neighbors' ctx ++ ns) rest
  dfs (n:ns) graph =                         -- visited n
    dfs ns graph
  

  一个非常简单的递归函数 . 要将其转换为广度优先搜索，我们所要做的就是用队列替换我们的堆栈边界：不是将邻居放在列表的前面，而是将它们放在后面：

  bfs _frontier Empty = []
  bfs [] _graph = []
  bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
    bfs (ns ++ neighbors' ctx) rest
  bfs (n:ns) graph =                         -- visited n
    bfs ns graph
  

  是的，我们必须做一些特别的事情来跟踪我们访问的节点，因为我们在图表上进行了渲染，就像我们没有访问过一样：每次我们递归时，我们只得到图表的一部分我们没有没见过 .

  回复于 2024-05-02T15:57:09+08:00
• 3

  请参阅example implementation of BFS，并在Martin Erwig: Inductive Graphs and Functional Graph Algorithms中进行说明 . 此外，DFS implementation，基于David King , John Launchbury: Structuring Depth-First Search Algorithms in Haskell

  （S.O.警察的提示：是的，这看起来像是一个仅限链接的答案，但这就是科学的工作方式 - 你必须真正阅读论文，重新输入他们的摘要并不是很有用 . ）

  回复于 2024-05-02T15:57:09+08:00
• 11

  在函数内隐藏一个可变状态是可以的 . 如果它不可见，则它不存在 . 我通常使用哈希集 . 但总的来说，如果您的分析指出了这一点，您应该坚持这一点 . 否则，只需使用设置数据结构 . OCaml拥有一套基于热切 balancer 的AVL树的优秀套装 .

  回复于 2024-05-02T15:57:09+08:00