Как я могу написать алгоритм MST (Prim или Kruskal) в Haskell?
-
28-09-2019 - |
Вопрос
Я могу написать как алгоритмы Прими, так и Крускала, чтобы найти минимальное охваченное дерево в C ++ или Java, но я хочу знать, как их реализовать в Haskell с O (MLOGM) или O (MLOGN) (чистые функциональные программы лучше). Большое спасибо.
Решение
Как говорит Svenningsson, Очередь поиска приоритета Хорошо подходит как для Крускала, так и для Прими (по крайней мере, автор провозглашает его в его бумага,) Проблема с Крускалом в том, что она требует, чтобы у вас был O (log n) Алгоритм поиска союза. Отказ Описана Datastructure профсоюза с чисто функциональным интерфейсом здесь, но он использует соревнованное состояние внутренне, и чисто функциональная реализация может быть невозможным и на самом деле, существует несколько проблем, где эффективное чисто функциональное решение не известно, как обсуждалось в это Связанный такой вопрос.
Неизвестный альтернативный доступ заключается в реализации алгоритма поиска союза в монаде ST. Поиск по взлому находит, что эквивалентность Пакет устраивает наши потребности. Ниже приведена реализация 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) времени, используя массивы или просто отслеживать вес в списке ввода, но это не совсем часть алгоритма.
Другие советы
Вот сырая крушкальная реализация.
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/
Я думаю, что очередь поиска приоритета - это то, что вы ищете. Он может быть оптимально реализован на функциональном языке, как продемонстрировано Ralf Hinze в бумага. Отказ Похоже, в бумаге доступен только через библиотеку ACM по стоимости.