كيفية توليد وظيفي عرض الشجرة أولاً. (مع هاسكل)

Question

لنفترض أن لدي نوع شجرة هاسكل التالي ، حيث "الحالة" عبارة عن غلاف بسيط:

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

لديّ أيضًا وظيفة "توسيع :: شجرة A -> شجرة A" التي تأخذ عقدة ورقة ، وتوسيعها إلى فرع ، أو يأخذ فرعًا ويعيدها دون تغيير. يمثل هذا النوع من الشجرة شجرة بحث N.

البحث الأول هو مضيعة ، حيث من الواضح أن مساحة البحث لا حصر لها ، حيث يمكنني الاستمرار بسهولة في توسيع نطاق البحث مع استخدام التوسع على جميع أوراق الشجرة ، وفرص فقدان الحالة الهدف عن طريق الخطأ ضخم ... وبالتالي فإن الحل الوحيد هو البحث الأول عن العرض ، وتم تنفيذه لائقًا جدًا هنا, ، والذي سيجد الحل إذا كان هناك.

ما انا تريد لتوليد ، رغم ذلك ، هي الشجرة التي تم اجتيازها يصل إلى إيجاد الحل. هذه مشكلة لأنني أعرف فقط كيفية القيام بهذا العمق الأول ، والتي يمكن القيام بها ببساطة تسمى وظيفة "التوسع" مرارًا وتكرارًا على عقدة الطفل الأولى ... حتى يتم العثور على حالة هدف. (هذا لن يولد أي شيء آخر ثم قائمة غير مريحة حقًا.)

هل يمكن لأي شخص أن يعطيني أي تلميحات حول كيفية القيام بذلك (أو خوارزمية بأكملها) ، أو حكم بشأن ما إذا كان ذلك ممكنًا أم لا مع التعقيد اللائق؟ (أو أي مصادر على هذا ، لأنني وجدت القليل منها.)

Answer 1

هل نظرت إلى كريس أوكاساكي "ترقيم العرض الأول: دروس من تمرين صغير في تصميم الخوارزمية"؟ ال 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 على حثني بعيدًا عن عادات هيكل التحكم القديمة. آمل أن يكون هذا الإصدار أكثر قبولًا.)

Answer 2

أنا فضولي لماذا تحتاج إلى 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), ، لأن فروع أكثر اليسار هي سلسلة لا نهاية لها من 2s.