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

Question

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

Answer 1

Как следует svenningsson, priority search queue хорошо подходит как для Краскала и Прима (по крайней мере, автор провозглашает его в paper.) Проблема с Крускала является то, что она требует, чтобы у вас есть O (Log п) union-find algorithm. Структурная структура структуры соединения с чисто функциональным интерфейсом описана here, но она использует изменчивое состояние внутри страны, и чисто функциональная реализация может быть невозможной, и на самом деле существует несколько проблем, когда эффективное чисто функциональное решение неизвестно, как описано в this Связанный вопрос.

Нечистый альтернативный вариант заключается в реализации алгоритма объединения-поиска в монаде ST. Поиск в Hackage показывает, что пакет equivalence подходит для наших нужд. Ниже приводится реализация Крускала с использованием Data.Equivalence.Monad из equivalence пакета:

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)) времени, это c a быть улучшено до O (1) раз, используя массивы или просто отслеживая вес во входном списке, но это не является частью алгоритма.

Answer 2

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

Answer 3

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

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

[Update]

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