9

假设我有以下 Haskell 树类型，其中“State”是一个简单的包装器：

data Tree a = Branch (State a) [Tree a]
            | Leaf   (State a)
            deriving (Eq, Show)

我还有一个函数“expand :: Tree a -> Tree a”，它接受一个叶节点，并将其展开为一个分支，或者采用一个分支并原样返回。这种树类型表示 N 元搜索树。

搜索深度优先是一种浪费，因为搜索空间显然是无限的，因为我可以通过在所有树的叶节点上使用 expand 轻松地继续扩展搜索空间，并且有可能意外错过目标状态是巨大的......因此唯一的解决方案是广度优先搜索，在这里实现得相当不错，如果它在那里，它将找到解决方案。

不过，我想要生成的是遍历查找解决方案的树。这是一个问题，因为我只知道如何进行深度优先，这可以通过简单地在第一个子节点上一次又一次地调用“扩展”函数来完成......直到找到目标状态。（除了一个非常不舒服的列表之外，这真的不会产生任何东西。）

谁能给我任何关于如何做到这一点（或整个算法）的提示，或者判断它是否可能具有相当的复杂性？（或者这方面的任何资料，因为我发现很少。）

4

2 回答 2

10

你看过 Chris Okasaki 的“广度优先编号：算法设计小练习的教训”吗？该Data.Tree模块包括一个名为的一元树构建器，该构建器unfoldTreeM_BF使用改编自该论文的算法。

这是我认为与您正在做的事情相对应的示例：

假设我想搜索一个无限二叉树的字符串，其中所有左孩子都是父字符串加“a”，右孩子是父字符串加“bb”。我可以使用unfoldTreeM_BF搜索树广度优先并将搜索到的树返回到解决方案：

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”，我会得到我想要的：

|
+- a
|  |
|  +- aa
|  |  |
|  |  +- aaa
|  |  |
|  |  `- aabb
|  |
|  `- abb
|
`- bb
   |
   +- bba
   |
   `- bbbb

如果这是您所描述的那种事情，那么适应您的树类型应该不难。

更新：这是一个免费的版本expand，以防您遇到这种情况：

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 促使我摆脱旧的控制结构习惯。我希望这个版本更容易接受。）

于 2010-05-15T04:02:33.243 回答
5

我很好奇你为什么需要这个expand函数——为什么不简单地递归地构造整个树并执行你想要的任何搜索呢​​？

如果您使用expand以跟踪搜索检查了哪些节点，那么构建一个列表似乎更简单，甚至是第二个树结构。

这是一个简单的示例，它只返回它找到的第一个结果，并Leaf删除了虚假的构造函数：

data State a = State { getState :: a } deriving (Eq, Show)

data Tree a = Branch { 
    state :: State a, 
    children :: [Tree a]
    } deriving (Eq, Show)

breadth ts = map (getState . state) ts ++ breadth (concatMap children ts)
search f t = head $ filter f (breadth [t])

mkTree n = Branch (State n) (map mkTree [n, 2*n .. n*n])

testTree = mkTree 2

在 GHCi 中试用：

> search (== 24) testTree
24

相比之下，这是一个简单的深度优先搜索：

depth (Branch (State x) ts) = x : (concatMap depth ts)
dSearch f t = head $ filter f (depth t)

...当然在使用 搜索时无法终止(== 24)，因为最左边的分支是无穷无尽的 2 序列。

于 2010-05-15T03:25:58.953 回答