كيف يمكنني كتابة خوارزمية MST (Prim أو Kruskal) في Haskell؟

Question

يمكنني كتابة خوارزميات Prim's و Kruskal للعثور على شجرة تمتد على الأقل في C ++ أو Java ، لكنني أريد أن أعرف كيفية تنفيذها في Haskell مع O (MLOGM) أو O (Mlogn) (البرامج الوظيفية الخالصة أفضل). شكرًا جزيلاً.

Answer 1

كما يقترح Svenningsson ، قائمة انتظار البحث الأولوية مناسبة تمامًا لكل من Kruskal's و Prim's (على الأقل يعلن المؤلف في كتابه ورق.) المشكلة مع Kruskal هي أنه يتطلب أن يكون لديك O (log n) خوارزمية الاتحاد. تم وصف بنية دائرة عدوانية الاتحاد مع واجهة وظيفية بحتة هنا, ولكنه يستخدم حالة قابلة للتغيير داخليًا ، وقد يكون التنفيذ الوظيفي البحت مستحيلًا ، وفي الواقع ، هناك العديد من المشكلات التي لا يُعرف فيها الحل الوظيفي الفعال ، كما تمت مناقشته في هذه ذات صلة لذلك السؤال.

يتمثل تغيير غير متخلف في تنفيذ خوارزمية عدوانية الاتحاد في St Monad. يجد البحث على Hackage أن التكافؤ الحزمة تناسب احتياجاتنا. فيما يلي تطبيق Kruskal باستخدام data.equivalence.monad من التكافؤ حزمة:

import Data.Equivalence.Monad
import Data.Graph as G
import Data.List(sortBy)
import Data.Map as M
import Control.Monad(filterM)
import Data.Ord(comparing)

run = runEquivM (const ()) (const $ const ())

kruskal weight graph = run $
 filterM go (sortBy (comparing weight) theEdges)
     where
      theEdges = G.edges graph
      go (u,v) = do 
        eq <- equivalent u v
        if eq then return False else
         equate u v >> return True

يمكن استخدامه مثل هذا:

fromL xs = fromJust . flip M.lookup (M.fromList xs)

testWeights = fromL [((1,2),1),((2,3),4),((3,4),5),((1,4),30),((1,3),4)]
testGraph = G.buildG  (1,4) [(1,2),(2,3),(3,4),(1,4),(1,3)]
test = kruskal testWeights testGraph

واختبار التشغيل يعطي:

[(1,2),(1,3),(3,4)]

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

Answer 2

هنا تنفيذ خام كروسكال.

import Data.List(sort)
import Data.Set (Set, member, fromList, insert, union)

data Edge a = Edge a a Double deriving Show

instance (Eq a) => Eq (Edge a) where
  Edge x1 y1 z1 == Edge x2 y2 z2 = x1 == x2 && y1 == y2 && z1 == z2

instance Eq a => Ord (Edge a) where
  (Edge _ _ x) `compare` (Edge _ _ y) = x `compare` y

kruskal :: Ord a => [Edge a] -> [Edge a]
kruskal = fst . foldl mst ([],[]) . sort

mst :: Ord a => ([Edge a],[Set a]) -> Edge a -> ([Edge a],[Set a])
mst (es, sets) e@(Edge p q _) = step $ extract sets where
   step (rest, Nothing, Nothing) = (e : es, fromList [p,q] : rest)
   step (rest, Just ps, Nothing) = (e : es, q `insert` ps : rest)
   step (rest, Nothing, Just qs) = (e : es, p `insert` qs : rest)
   step (rest, Just ps, Just qs) | ps == qs = (es, sets) --circle
                                 | otherwise = (e : es, ps `union` qs : rest)
   extract = foldr f ([], Nothing, Nothing) where
       f s (list, setp, setq) =
            let list' = if member p s || member q s then list else s:list
                setp' = if member p s then Just s else setp
                setq' = if member q s then Just s else setq
            in (list', setp', setq') 

الخطوة الأولى هي فرز الحواف ، وهي O (n log n). المشكلة هي العثور على بحث أسرع لمجموعات قمة الرأس في وظيفة الاستخراج. لم أتمكن من العثور على حل أسرع لهذا ، ربما يكون لدى شخص ما فكرة ...

تحديث

بالنسبة لتطبيق Scala ، استخدمت بنية بيانات تشبه الخريطة لأداء أفضل (نأمل) ، ولكن لسوء الحظ ، يستخدم مجموعات قابلة للتغيير ، وليس لدي أدنى فكرة عن كيفية ترجمة هذا إلى Haskell. الكود في مدونتي (آسف ، الوصف باللغة الألمانية): http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Answer 3

أعتقد أن قائمة انتظار البحث ذات الأولوية هي ما تبحث عنه. يمكن تنفيذه على النحو الأمثل بلغة وظيفية كما يتضح من Ralf Hinze In ورقة. يبدو أن الورقة متوفرة فقط عبر مكتبة ACM بتكلفة.