haskell - Haskell 中的广度优先遍历

Question

我需要在树状结构中找到所有路径。

我最近将深度优先遍历（或迭代）定义如下：

dfIterate:: (a -> [a]) -> a -> [[a]]
dfIterate f a = map (a:) ([] : concatMap (dfIterate f) (f a))

它需要一个种子a和一个函数a -> [a]（从每个“ a”，你可以得到多个a）。结果是从种子开始的路径列表。它运作良好：

ghci> let f a = if a == 1 then [2, 3] else if a == 2 then [4] else []
ghci> dfIterate f 1
[[1],[1,2],[1,2,4],[1,3]]

我的函数dfIterate正确迭代并向我显示所有路径。该函数f模拟上面的树。

但是如何进行“广度优先遍历”呢？这种情况下的结果应该是：[[1],[1,2],[1,3],[1,2,4]]. 我的第一次尝试：

bfIterate :: (a -> [a]) -> [a] -> [[a]]
bfIterate _ [] = [[]]
bfIterate f (a:as) = map (a:) (bfIterate f (as ++ (f a)))

我尝试将第二个参数用作队列。我知道我离结果还很远......谢谢

编辑：此链接提供了有趣的方法：Breadth-First Search using State monad in Haskell。但是，我的问题是寻找所有路径（即[[a]]），而该问题是寻找单一解决方案（即[a]）

标签： haskelltreebreadth-first-search

Answer 1

先正确，后效率。

bfPaths :: (a -> [a]) -> a -> [[a]]
bfPaths step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = path :
   go (q ++ [ (x, path ++ [x]) | x <- step s ])

确实维护一个队列并将节点逐级添加到其中。

go的参数是一个列表，用作“先进先出”队列。它包含成对的(node_value, that_node's_path). 初始节点值为seed，因此其路径为[seed]。

在每一步，队列都被解构为头对(s, path)和队列的其余部分q。然后path返回它，然后是处理其余部分的结果q，以及由step函数从这个种子产生的下一个对s，附加在q:之后(q ++ [....])。

在每个步骤的列表末尾附加会产生一个队列，而前置会产生一个“后进先出”堆栈。

因此，该列表被用作“待办事项”列表、“议程”或探索此隐式图的前沿。使用队列，探索是广度优先的；使用堆栈它是深度优先的。

尝试一下：

> bfPaths f 1
[[1],[1,2],[1,3],[1,2,4]]

现在您可以寻找提高效率的方法。特别是，重复附加单例列表以构建结果列表会导致二次行为。执行时间将随着输入大小的平方增长。

---

最简单的改进是反向构建路径，然后将它们反向返回（或仅在最终处理时反向，如果必须），从而避免二次减速：

bfPathsR :: (a -> [a]) -> a -> [[a]]
bfPathsR step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = path :
   go (q ++ [ (x, [x] ++ path) | x <- step s ])

看起来它也是最好的，因为它允许在构建路径（反向）时最大程度地共享结构，当然在前面添加新值是O(1)，所以总的来说它是线性的（执行时间随着输入的大小而增长）。

如果您只想输出已完成的路径，即没有延续的路径，您只需将此条件添加到代码中：

bfPathsRC :: (a -> [a]) -> a -> [[a]]
bfPathsRC step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = [path | null next] ++
   go (q ++ [ (x, [x] ++ path) | x <- next ])
  where
  next = step s

-- bfPathsRC f 1  =  [[3,1],[4,2,1]]