9

次のHaskellツリータイプがあるとします。ここで、「State」は単純なラッパーです。

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

また、リーフノードを取得してブランチに展開する関数「expand :: Tree a-> Tree a」、またはブランチを取得して変更せずに返す関数もあります。このツリータイプは、N-ary検索ツリーを表します。

深さ優先探索は無駄です。検索スペースは明らかに無限であり、ツリーのすべてのリーフノードでexpandを使用して検索スペースを簡単に拡張し続けることができ、誤ってゴール状態を見逃す可能性があります。巨大です...したがって、唯一の解決策は幅優先探索であり、ここでかなり適切に実装されています。そこにある場合は解決策が見つかります。

しかし、私が生成したいのは、解決策を見つけるためにトラバースされたツリーです。これは問題です。なぜなら、私はこの深さ優先を行う方法しか知らないからです。これは、最初の子ノードで「expand」関数を何度も呼び出すだけで実行できます...ゴール状態が見つかるまで。（これは、本当に不快なリスト以外のものを実際に生成することはありません。）

誰かが私にこれを行う方法（またはアルゴリズム全体）についてのヒント、またはそれがまともな複雑さで可能かどうかについての評決を教えてもらえますか？（または、これに関する情報源は、かなり少ないので。）

4

2 に答える 2

10

クリス・オカサキの「幅優先探索：アルゴリズム設計の小さな演習からの教訓」を見たことがありますか？このモジュールには、その論文から採用されたアルゴリズムを使用する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検索によって調べられるノードを追跡するために使用している場合は、リストを作成する方が簡単であるか、2番目のツリー構造でさえあるように見えます。

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 に答える