HaskellでMSTアルゴリズム（PrimまたはKruskal）を書くにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/4290163

質問

PrimとKruskalの両方のアルゴリズムを書いて、C ++またはJavaで最小スパニングツリーを見つけることができますが、O（MLOGM）またはO（MLogn）でHaskellでそれらを実装する方法を知りたいと思います（純粋な機能プログラムの方が優れています）。どうもありがとう。

役に立ちましたか？

解決

スベンニングソンが示唆するように、 優先検索キュー KruskalとPrim'sの両方に適しています（少なくとも著者は彼でそれを宣言しています 論文。）Kruskalの問題は、O（log n）を持っていることが必要であることです ユニオンファインドアルゴリズム. 。純粋に機能的なインターフェイスを備えた組合ファインドデータストラクチャについて説明します ここ, 、しかし、それは内部的に可変状態を使用し、純粋に機能的な実装は不可能かもしれません。 これ 関連する質問。

非純粋な変更は、セントモナドに組合ファインドアルゴリズムを実装することです。ハッキングの検索では、次のことがわかります 等価 パッケージは私たちのニーズに合っています。以下は、data.ecivalence.monadを使用してKruskalの実装です。 等価 パッケージ：

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/

優先検索キューはあなたが探しているものだと思います。ラルフヒンゼによって示されるように、機能的な言語で最適に実装できます 論文. 。この論文は、ACMのライブラリからのみ利用できるようです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top