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)]]

如果元组的第二个元素与另一个元组的第一个元素匹配，则两个元组可以连接，即：一个元组是(_,a)，另一个元组是 like (a,_)。

对此最有效的实施是什么？我需要找到最适合它的数据结构。有什么建议么 ？我将在其中执行算法的元组数量将超过 400,000。

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 然后

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

您可以标准化一个路径，将其旋转 n 次并采用“head . sortBy toBase10 . rotations”。

于 2013-02-05T12:18:01.397 回答
1

我认为您的问题适合 NP 类别，因为：

哈密​​顿路径，也称为哈密顿路径，是图的两个顶点之间的路径，每个顶点恰好访问一次。

一般来说，寻找哈密顿路径的问题是 NP 完全的（Garey and Johnson 1983, pp. 199-200），因此唯一已知的确定给定一般图是否具有哈密顿路径的方法是进行穷举搜索（来源）

您的问题甚至“更难”，因为您事先不知道最终节点是什么。

在数据结构方面可以尝试模拟 Haskell 中的哈希表结构，因为这种数据类型在图形中很常用，你的问题可以转化为图形。

于 2013-02-05T12:19:07.013 回答