功能广度优先搜索

Question

功能深度优先搜索在有向无环图中很可爱.

然而,在带循环的图中,我们如何避免无限递归？在程序语言中,我会在我点击它时标记节点,但是让我说我​​不能这样做.

访问节点列表是可能的,但速度很慢,因为使用一个会导致在重复之前对该列表进行线性搜索.比这里的列表更好的数据结构显然会有所帮助,但这不是游戏的目的,因为我在ML中编码 - 列表是王道,还有其他任何我必须自己写的东西.

这个问题有巧妙的方法吗？或者我是否必须处理访问列表或上帝禁止,可变状态？

Answer 1

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

有关更温和的介绍(有插图!),请参阅我的博客文章"使用感应图生成迷宫".

使用归纳图的技巧是它们允许您在图形上进行模式匹配.使用列表的常用功能习惯是将它们分解为头元素和列表的其余部分,然后对其进行递归:

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

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

节点上的模式匹配http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/match1.png

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

这让我们可以编写一个mapfor图(在Haskellish伪代码中可以用模式同义词实现):

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

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

为了克服这个问题,我们添加了另一个构造:一个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

是的,这就是我们所需要的!当我们对图表进行递归时,我们不需要做任何特殊的事情来跟踪我们访问过的节点,就像我们不必跟踪我们访问过的列表单元格一样:每次我们递归时,我们都会"只得到我们还没有看到的图表的一部分.

Answer 2

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

Answer 3

参见BFS的示例实现,以及Martin Erwig中的解释:归纳图和功能图算法.此外,DFS实现,基于David King,John Launchbury:在Haskell中构建深度优先搜索算法

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