3

リストのタプルを考えると、そこからすべての一意のパスを見つける必要があります。

Example I/P: [(1,2),(2,3),(3,4),(9,11),(4,5),(5,6),(6,7),(3,9)]
O/P: [[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)],[(1,2),(2,3),(3,9),(9,11)]]

タプルの2番目の要素が他のタプルの最初の要素と一致する場合、2つのタプルを接続できます。つまり、1つのタプルは(_,a)で、他のタプルはのようになり(a,_)ます。

このための最も効率的な実装は何ですか？それに適した最適なデータ構造を見つける必要があります。助言がありますか ？アルゴリズムを実行するタプルの数は40万以上になります。

4

2 に答える 2

3 
{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.List (permutations, nub)

path :: Eq a => [(a, a)] -> [(a, a)]
path [] = []
path [x] = [x]
path (u@(_, a):v@(b, _):xs) = if a == b then u:path (v:xs) else [u]

allPaths = nub . map path . permutations

（チェーン生成を最適化することはできますが、この問題には指数関数的な時間計算量があると思います）

編集済み

一般に、どのパスを返すかをより正確に定義する必要があります。

サイクル不変（[（1,2）、（2,3）、（3,1）] == [（2,3）、（3,1）、（1,3）]）を無視すると、すべてのパスを生成できます（順列を使用せずに）

{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.List (permutations, nub, sortBy, isInfixOf)

data Tree a = Node a [Tree a] deriving Show

treeFromList :: Eq a => a -> [(a, a)] -> Tree a
treeFromList a [] = Node a []
treeFromList a xs = Node a $ map subTree $ filter ((a==).fst) xs
  where subTree v@(_, b) = treeFromList b $ filter (v/=) xs

treesFromList :: Eq a => [(a, a)] -> [Tree a]
treesFromList xs = map (flip treeFromList xs) $ nub $ map fst xs ++ map snd xs

treeToList :: Tree a -> [[a]]
treeToList (Node a []) = [[a]]
treeToList (Node a xs) = [a:ws | ws <- concatMap treeToList xs]

treesToList :: [Tree a] -> [[a]]
treesToList = concatMap treeToList

uniqTrees :: Eq a => [[a]] -> [[a]]
uniqTrees = f . reverse . sortBy ((.length).compare.length)
  where f [] = []
        f (x:xs) = x: filter (not.flip isInfixOf x) (f xs)

allPaths = uniqTrees . treesToList . treesFromList

それから

*Main> allPaths [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 1)]
[[2,4,1,2,3,4],[2,3,4,1,2,4],[1,3,4,1,2,4],[1,3,4,1,2,3],[1,2,4,1,3,4],[1,2,3,4,1,3]]

uniqTrees効率が悪く、一般に、多くの最適化を行うことができます。

サイクル不変を回避したい場合は、前の例で最小のbase10表現を選択してサイクルを正規化できます（[（1,2）、（2,3）、（3,1）] == [（2,3）、 （3,1）、（1,3）]）1231 <2313 then

normalize [(2,3),(3,1),(1,3)] == [(1,2),(2,3),(3,1)]

パスをn回回転させ、「head.sortBytoBase10.rotations」を取ることができます。

于 2013-02-05T12:18:01.397 に答える
1

次の理由から、あなたの問題はNPカテゴリに当てはまると思います。

ハミルトンパスとも呼ばれるハミルトンパスは、グラフの2つの頂点間のパスであり、各頂点に1回だけアクセスします。

一般に、ハミルトン経路を見つける問題はNP完全であるため（Garey and Johnson 1983、pp。199-200）、特定の一般的なグラフにハミルトン経路があるかどうかを判断する唯一の既知の方法は、徹底的な検索を行うことです（ソース）

エンドノードが何になるかを事前に知らないため、問題はさらに「困難」になります。

データ構造に関しては、Haskellでハッシュテーブル構造をシミュレートすることができます。これは、このデータ型がグラフで一般的に使用されており、問題がグラフに変わる可能性があるためです。

于 2013-02-05T12:19:07.013 に答える