Как я могу написать алгоритм MST (Prim или Kruskal) в Haskell? - PullRequest
Новая
       49

Как я могу написать алгоритм MST (Prim или Kruskal) в Haskell?

5 голосов
/ 27 ноября 2010

Я могу написать как алгоритмы Прима, так и Крускала, чтобы найти минимальное связующее дерево в C ++ или Java, но я хочу знать, как реализовать их в Haskell с O (mlogm) или O (mlogn) (лучше чисто функциональные программы) , Большое спасибо.

Ответы [ 3 ]

10 голосов
/ 27 ноября 2010

Как предполагает Свеннингссон, приоритетная очередь поиска хорошо подходит как для Крускала, так и для Прима (по крайней мере, автор объявляет об этом в своей статье .) Проблема с Крускалом заключается в том, что она требуету вас есть O (log n) алгоритм поиска объединения .Структура соединения с поиском объединения с чисто функциональным интерфейсом описана здесь , но она использует изменяемое состояние внутри, и чисто функциональная реализация может быть невозможна, и на самом деле, есть несколько проблем, когда эффективное чисто функциональное решениенеизвестно, как обсуждалось в этом связанном вопросе SO.

Неприменимой альтернативой является реализация алгоритма поиска объединения в монаде ST.Поиск в 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) времени, используя массивы или просто отслеживая вес в списке ввода, но на самом деле это не часть алгоритма.

6 голосов
/ 28 ноября 2010

Вот грубая реализация Крускала. 

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). Проблема состоит в том, чтобы найти более быстрый поиск наборов вершин в функции извлечения. Я не мог найти более быстрое решение для этого, может быть, у кого-то есть идея ...

[Update]

Для реализации Scala я использовал подобную карте структуру данных для (надеюсь) повышения производительности, но, к сожалению, он использует изменяемые наборы, и я понятия не имею, как перевести это на Haskell. Код в моем блоге (извините, описание на немецком языке): http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

3 голосов
/ 27 ноября 2010

Я думаю, что приоритетной поисковой очередью является то, что вы ищете. Он может быть оптимально реализован на функциональном языке, как продемонстрировал Ральф Хинце в статье . Кажется, что статья доступна только через библиотеку ACM по цене.

...