Ich kann Prims und Kruskals Algorithmen schreiben, um einen minimalen Spannbaum in C++ oder Java zu finden, aber ich möchte wissen, wie man sie in Haskell mit O (mlogm) oder O (mlogn) implementiert (reine Funktionsprogramme sind besser). Danke vielmals.Wie kann ich einen MST-Algorithmus (Prim oder Kruskal) in Haskell schreiben?
Antwort
Wie Svenningsson schon sagt, ist priority search queue gut geeignet sowohl für Kruskals und Prim (atleast der Autor verkündet er in seiner paper.) Das Problem mit Kruskal ist, dass es erfordert, dass Sie einen O haben (log n) union-find algorithm. Eine Union-find-Datenstruktur mit einer rein funktionalen Schnittstelle wird here beschrieben, verwendet jedoch intern einen änderbaren Zustand, und eine rein funktionale Implementierung ist möglicherweise unmöglich, und tatsächlich gibt es mehrere Probleme, bei denen eine effiziente rein funktionale Lösung nicht bekannt ist this Verwandte SO Frage.
Eine nicht-reine Alternative ist die Implementierung von union-find-Algorithmus in der ST-Monade. Eine Suche auf Hackage findet, dass das equivalence Paket unseren Bedürfnissen entspricht. Es folgt eine Implementierung von Kruskal mit Data.Equivalence.Monad aus dem equivalence Paket:
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
Es kann wie folgt verwendet werden:
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
und Lauftest ergibt:
[(1,2),(1,3),(3,4)]
Es sollte angemerkt werden, dass die Laufzeit von Gewichten abhängig ist, die in O (1) Zeit laufen, jedoch erzeugt fromL
eine Gewichtungsfunktion, die in O (log (n)) Zeit läuft, dies c Eine Verbesserung auf O (1) Zeit durch die Verwendung von Arrays oder einfach das Gewicht in der Input-Liste zu verfolgen, aber es ist nicht wirklich Teil des Algorithmus.
Es scheint, dass es eine effiziente persistente Implementierung gibt: www.lri.fr /~filliatr/ftp/publis/puf-wml07.ps – Landei
@Landei, so scheint es, ich werde meine Antwort aktualisieren, sobald ich etwas darüber nachgeforscht habe. – HaskellElephant
Ich denke, eine Prioritätssuchwarteschlange ist, was Sie suchen. Es kann optimal in einer funktionalen Sprache implementiert werden, wie von Ralf Hinze in a paper demonstriert. Es scheint, als ob die Zeitung nur gegen eine Gebühr in der Bibliothek von acm erhältlich ist.
Der Artikel ist hier verfügbar: (http://portal.acm.org/ft_gateway.cfm?id=507650&type=pdf&coll=GUIDE&dl=GUIDE&CFID=74270503&CFTOKEN=40353710 – HaskellElephant
Hier ist eine grobe Kruskal-Implementierung.
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) [email protected](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')
Der erste Schritt ist das Sortieren der Kanten, die O (n log n) ist. Das Problem besteht darin, eine schnellere Suche nach den Scheitelpunktgruppen in der Extraktfunktion zu finden. Ich konnte nicht eine schnellere Lösung hierfür finden, vielleicht jemand eine Idee ...
[Update]
Für eine Scala Implementierung I hat eine kartenähnliche Datenstruktur für (hoffentlich) verwenden eine bessere Leistung, aber leider verwendet es veränderbare Sätze, und ich habe keine Ahnung, wie man das in Haskell übersetzt. Der Code ist in meinem Blog: http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/
Können Sie erklären, was ist Ihr Problem mit der Implementierung? Es ist einfacher, dir zu helfen, wenn wir wissen, was dein Problem ist. – fuz
Das Problem betrifft hauptsächlich Array. –
Prim benötigt ein Array, um aufzuzeichnen, ob der Knoten ausgewählt wurde, und Kruskal benötigt den Union-Suchsatz. Das Ändern eines Arrays kostet viel. –