¿Cómo puedo escribir un algoritmo MST (Prim o de Kruskal) en Haskell?
-
28-09-2019 - |
Pregunta
Puedo escribir tanto algoritmos de Kruskal de Prim y para encontrar un árbol de expansión mínima en C ++ o Java, pero me gustaría saber cómo ponerlas en práctica en Haskell con O (mlogm) o S (mlogn) (programas funcionales puro es mejor) . Muchas gracias.
Solución
Como sugiere Svenningsson, cola de búsqueda prioritaria es muy adecuado para ambas Kruskal de y Prim de (al menos el autor proclama en su papel .) El problema de Kruskal es que requiere que usted tiene una O (log n) unión-algoritmo . Una estructura de datos unión-con una interfaz puramente funcional se describe aquí , pero utiliza el estado mutable internamente, y una aplicación puramente funcional podría ser imposible y, de hecho, hay varios problemas en los que no se conoce una solución puramente funcional eficiente, como se discute en esta pregunta SO relacionado.
A alterenative no puro es implementar algoritmo de unión-en la mónada ST. Una búsqueda en Hackage encuentra que el href="http://hackage.haskell.org/package/equivalence" rel="nofollow noreferrer"> equivalencia paquete equivalencia paquete Puede ser utilizado como esto: y prueba de funcionamiento da: Debe tenerse en cuenta que el tiempo de funcionamiento depende de los pesos que se ejecutan en O (1) tiempo, sin embargo 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)]
fromL
crea una función de ponderación que se ejecuta en tiempo O (log (n)), esto puede ser mejorado a O (1) tiempo utilizando matrices o simplemente no perder de vista el peso en la lista de entrada, pero no es realmente parte del algoritmo.
Otros consejos
Esta es una aplicación de Kruskal crudo.
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')
El primer paso es la clasificación de los bordes, que es O (n log n). El problema es encontrar una forma más rápida de consulta para los conjuntos de vértices en la función de extracción. No pude encontrar una solución más rápida para esto, tal vez alguien tiene una idea ...
[Actualización]
Para una implementación Scala que utiliza una estructura de datos en forma de mapa para (esperemos) un mejor rendimiento, pero por desgracia, utiliza conjuntos mutables, y no tengo ni idea de cómo traducir esto en Haskell. El código está en mi blog (lo siento, descripción está en alemán): http: / /dgronau.wordpress.com/2010/11/28/nochmal-kruskal/
creo una cola de prioridad de búsqueda es lo que estás buscando. Se puede implementar de manera óptima en un lenguaje funcional como se demuestra por Ralf Hinze en un documento . Parece que el documento sólo está disponible a través de la biblioteca de acm a un costo.