我需要一些帮助来实现 Haskell 的最长路径算法。我只使用 Haskell 大约两周,之前没有用函数式语言做过任何事情。当您受限于不可变数据和递归时,当我试图用函数式语言实现算法时,我真的很迷茫。
我一直在尝试实现这个算法:http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
我的图是这样构造的:
data = Graph w = Graph {vertices :: [(Char, w)],
edges :: [(Char, Char, w)]} deriving Show
所以我在顶点和边上都有权重,权重可以是任何数据类型。因此,在计算最长路径时,我还需要使用两个函数,f
和 g
。从顶点 a
到 b
的最长路径将是 f(w)
和 g(w)
的总和> 对于路径中的所有权重。
我尝试过实现这个,但我总是发现自己在尝试以“命令式”的方式编写代码,这种方式很快就会变得非常丑陋......
请指出正确的方向。
weight_of_longest_path :: (Ord w) => Graph w -> Char -> Char
-> (w -> w) -> (w -> w) -> w
weight_of_longest_path (Graph v w) startVert endVert f g =
let
topSort = dropWhile (/= startVert) $ topological_ordering (Graph v w)
distList = zip topSort $
(snd $ head $ filter (\(a,b) -> a == startVert) v)
: (repeat (-999999999))
finalList = getFinalList (Graph v w) topSort distList f g
in
snd $ head $ filter (\(a,b) -> b == endVert) finalList
getFinalList :: (Ord w) => Graph w -> [Char] -> [(Char, w)]
-> (w -> w) -> (w -> w) -> [(Char, w)]
getFinalList _ [] finalList _ _ = finalList
getFinalList (Graph v w) (firstVert:rest) distList f g =
let
neighbours = secondNodes $ filter (\(a,b,w) -> a == firstVert) w
finalList = updateList firstVert neighbours distList (Graph v w) f g
in
getFinalList (Graph v w) rest finalList f g
updateList :: (Ord w) => Char -> [Char] -> [(Char, w)] -> Graph w
-> (w -> w) -> (w -> w) -> [(Char, w)]
updateList _ [] updatedList _ _ _ = updatedList
updateList firstVert (neighbour:rest) distList (Graph vertices weights) f g =
let
edgeWeight = selectThird $ head
$ filter (\(a,b,w) -> a == firstVert && b == neighbour) weights
verticeWeight = snd $ head
$ filter (\(a,b) -> a == neighbour) vertices
newDist = calcDist firstVert neighbour verticeWeight edgeWeight
distList f g
updatedList = replace distList neighbour newDist
in
updateList firstVert rest updatedList (Graph vertices weights) f g
calcDist :: (Ord w) => Char -> Char -> w -> w -> [(Char, w)]
-> (w -> w) -> (w -> w) -> w
calcDist firstVert neighbour verticeWeight edgeWeight distList f g =
if (compareTo f g
(snd $ head $ filter (\(a,b) -> a == neighbour) distList)
(snd $ head $ filter (\(a,b) -> a == firstVert) distList)
edgeWeight verticeWeight) == True
then
(f (snd $ head $ filter (\(a,b) -> a == firstVert) distList))
+ (g edgeWeight) + (f verticeWeight)
else
(f (snd $ head $ filter (\(a,b) -> a == neighbour) distList))
replace :: [(Char, w)] -> Char -> w -> [(Char, w)]
replace distList vertice value =
map (\p@(f, _) -> if f == vertice then (vertice, value) else p)
distList
如您所见,对于这样一个简单的算法,它有很多困惑的代码,我相信它可以以更简洁的方式实现。
最佳答案
这是一种采用更“函数式”思维方式的方法。它围绕两个功能展开:
longestPath :: Graph -> Node -> Node -> [Edge]
pathCost :: Graph -> [Edges] -> Int
longestPath
将路径作为最长路径的边列表返回。 pathCost
返回路径的成本。
longestPath
的定义是这样的:
longestPath g start end
| start == end = []
| otherwise =
maximumBy (comparing (pathCost g))
[ e : path | e <- edges of the node start
let start' = the other vertex of e,
let g' = graph g with node start deleted,
let path = longestPath g' start' end ]
(maximumBy
来自Data.List
和comparing
来自Data.Ord
)
注意边缘将以相反的顺序生成。
有许多实现细节需要弄清楚,特别是,当没有从 start
到 的路径时,您必须稍微修改它以处理这种情况node
(一旦开始删除节点就会发生这种情况),但这是我要开始的方法。
关于algorithm - 在 Haskell 中实现最长路径算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21811902/