如何在功能上生成树的广度优先。 （与Haskell） [英] How to functionally generate a tree breadth-first. (With Haskell)
问题描述
说我有以下Haskell树类型，其中状态是一个简单的包装：
Say I have the following Haskell tree type, where "State" is a simple wrapper:
data Tree a = Branch (State a) [Tree a]
| Leaf (State a)
deriving (Eq, Show)
我也有一个函数 expand :: Tree a-> Tree a，它接受一个叶节点
并将其展开为一个分支，或者接受一个分支并返回其原样。这种树类型代表N元搜索树。
I also have a function "expand :: Tree a -> Tree a" which takes a leaf node, and expands it into a branch, or takes a branch and returns it unaltered. This tree type represents an N-ary search-tree.
深度优先搜索是一种浪费，因为搜索空间显然是无限的，因此我可以轻松地继续通过在所有树的叶节点上使用expand来扩展搜索空间，并且偶然错过目标状态的机会是巨大的...因此，唯一的解决方案是广度优先搜索，在此处，如果有的话，它将找到解决方案。
Searching depth-first is a waste, as the search-space is obviously infinite, as I can easily keep on expanding the search-space with the use of expand on all the tree's leaf nodes, and the chances of accidentally missing the goal-state is huge... thus the only solution is a breadth-first search, implemented pretty decent over here, which will find the solution if it's there.
我想要生成的是遍历树的直到找到解决方案。
这是一个问题，因为我只知道深度优先，这可以通过在第一个子节点上反复调用 expand函数来完成，直到找到目标状态为止。 。 （除了真正令人不舒服的列表之外，这实际上不会生成其他任何东西。）
What I want to generate, though, is the tree traversed up to finding the solution. This is a problem because I only know how to do this depth-first, which could be done by simply called the "expand" function again and again upon the first child node... until a goal-state is found. (This would really not generate anything other then a really uncomfortable list.)
有人可以给我任何有关如何执行此操作的提示（或整个算法），或者判断是否有可能具有适当的复杂性？ （或其他相关资料，因为我发现的很少。）
Could anyone give me any hints on how to do this (or an entire algorithm), or a verdict on whether or not it's possible with a decent complexity? (Or any sources on this, because I found rather few.)
推荐答案
您是否看过克里斯·冈崎（Chris Okasaki）的宽度优先编号：算法设计中的小练习 ？ Data.Tree 模块包括一个名为 unfoldTreeM_BF 的单子树生成器，它使用从该论文改编的算法。
Have you looked at Chris Okasaki's "Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design"? The Data.Tree module includes a monadic tree builder named unfoldTreeM_BF that uses an algorithm adapted from that paper.
以下是我认为与您正在执行的操作相对应的示例：
Here's an example that I think corresponds to what you're doing:
假设我要搜索无限二叉树的字符串，其中所有左子级是父级字符串加上 a，右子级是父级加上 bb。我可以使用 unfoldTreeM_BF 广度优先搜索树，然后将搜索到的树返回到解决方案：
Suppose I want to search an infinite binary tree of strings where all the left children are the parent string plus "a", and the right children are the parent plus "bb". I could use unfoldTreeM_BF to search the tree breadth-first and return the searched tree up to the solution:
import Control.Monad.State
import Data.Tree
children :: String -> [String]
children x = [x ++ "a", x ++ "bb"]
expand query x = do
found <- get
if found
then return (x, [])
else do
let (before, after) = break (==query) $ children x
if null after
then return (x, before)
else do
put True
return (x, before ++ [head after])
searchBF query = (evalState $ unfoldTreeM_BF (expand query) []) False
printSearchBF = drawTree . searchBF
这不是很漂亮，但是可以。如果我搜索 aabb，我将得到我想要的：
This isn't terribly pretty, but it works. If I search for "aabb" I get exactly what I want:
|
+- a
| |
| +- aa
| | |
| | +- aaa
| | |
| | `- aabb
| |
| `- abb
|
`- bb
|
+- bba
|
`- bbbb
如果这是您要描述的内容，则不应
If this is the kind of thing you're describing, it shouldn't be hard to adapt for your tree type.
更新：这是 expand 的免费版本，如果您喜欢这种事情：
UPDATE: Here's a do-free version of expand, in case you're into this kind of thing:
expand q x = liftM ((,) x) $ get >>= expandChildren
where
checkChildren (before, []) = return before
checkChildren (before, t:_) = put True >> return (before ++ [t])
expandChildren True = return []
expandChildren _ = checkChildren $ break (==q) $ children x
（感谢camccann使我摆脱了旧的控制结构习惯。我希望此版本更容易接受。）
(Thanks to camccann for prodding me away from old control structure habits. I hope this version is more acceptable.)
这篇关于如何在功能上生成树的广度优先。 （与Haskell）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
