Wie man funktionell ein Baum Breiten erste erzeugen. (Mit Haskell)

Question

Sprich ich habe folgendes Haskell Baumtyp, in dem „Staat“ ist ein einfaches Wrapper:

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

Ich habe auch eine Funktion „erweitern :: Baum a -> Baum ein“, die einen Blattknoten nimmt, und dehnt sie sich in einen Zweig, oder nimmt einen Zweig und gibt sie unverändert. Dieser Baum Typ einen N-ary Suchbaum.

Sie suchen zuerst in die Tiefe ist eine Verschwendung, da der Suchraum offensichtlich unendlich ist, wie ich leicht auf den Ausbau der Suchraum bei der Verwendung von erweitern auf allen Blattknoten des Baumes zu halten, und die Chancen, aus Versehen die fehlenden Ziel-Zustand ist sehr groß ... also die einzige Lösung ist eine Breitensuche, implementiert ziemlich anständig über hier , was die Lösung finden, wenn es da ist.

Was ich will zu erzeugen, obwohl, ist der Baum Traversed bis , um die Lösung zu finden. Dies ist ein Problem, weil ich nur wissen, wie diese zuerst in der Tiefe, zu tun, die einfach getan werden könnten, die „erweitern“ Funktion immer wieder auf dem ersten Kind-Knoten genannt ..., bis ein Ziel-Zustand gefunden wird. (Dies würde wirklich nichts erzeugt andere dann eine wirklich unangenehme Liste.)

Kann jemand mir keine Hinweise, wie dies zu tun (oder einen ganzen Algorithmus) oder ein Urteil darüber, ob oder nicht, es ist möglich, mit einer anständigen Komplexität? (Oder irgendwelche Quellen zu diesem Thema, weil ich eher wenige gefunden.)

Answer 1

Haben Sie bei Chris Okasaki der sah "Breite-First-Nummerierung: Lehren aus einer kleinen Übung in Algorithm Design" ? Das Data.Tree Modul enthält einen monadischen Tree-Builder namens unfoldTreeM_BF, die einen Algorithmus aus diesem Papier angepasst verwendet.

Hier ist ein Beispiel, dass ich denke, entspricht dem, was Sie tun:

Angenommen, ich einen unendlichen binären Baum von Strings zu suchen, in dem alle die linken Kinder die Mutter Zeichenfolge plus „a“, und die richtigen Kinder sind die Eltern plus „bb“. Ich konnte unfoldTreeM_BF verwenden, um die Baumbreiten zuerst zu suchen und Rückkehr der Baum bis zur Lösung gesucht:

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

Das ist nicht sehr schön, aber es funktioniert. Wenn ich für „aabb“ suche bekomme ich genau das, was ich will:

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

Wenn dies die Art der Sache ist Sie beschreiben, sollte es nicht schwer sein, für Ihren Baum Typen anzupassen.

UPDATE: Hier ist eine Do-freie Version von expand, falls Sie sich in diese Art der Sache:

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

(Dank camccann für mich weg von alter Kontrollstruktur Gewohnheiten prodding. Ich hoffe, dass diese Version mehr akzeptabel ist.)

Answer 2

Ich bin neugierig, warum Sie die expand Funktion überhaupt brauchen - warum nicht einfach den gesamten Baum konstruiert rekursiv und ausführen, was auch immer suchen, die Sie wollen?

Wenn Sie mit expand, um die Knoten zu verfolgen durch die Suche untersucht werden, den Aufbau einer Liste, wie Sie gehen scheint einfacher, oder sogar eine zweite Baumstruktur.

Hier ist ein kleines Beispiel, dass nur das erste Ergebnis gibt es findet, mit dem falschen Leaf Konstruktor entfernt:

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

Der Versuch, es in GHCi aus:

> search (== 24) testTree
24

Für Kontrast, hier ist eine naive Tiefensuche:

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

... was natürlich zu beenden, schlägt fehl, wenn mit (== 24) der Suche, weil die am weitesten links gelegenen Zweige sind eine endlose Reihe von 2s.