幅優先のツリーを機能的に生成する方法。(Haskellあり)

StackOverflow https://stackoverflow.com/questions/2838670

質問

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

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

「expand ::」という関数もあります。ツリーA->ツリーA "これはリーフノードを取り、枝に拡張するか、枝を取り、変更されていないものを返します。このツリー タイプは N 分探索ツリーを表します。

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

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

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

役に立ちましたか？

解決

クリス・オカザキを見ましたか？ 「幅優先の番号付け:アルゴリズム設計の小さな演習から得た教訓」?の 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 に感謝します。このバージョンがより受け入れられることを願っています。)

他のヒント

なぜ必要なのか不思議です 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 だからです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top