时间戳

首页 > 解决方案 > 循环图上的记忆遍历

haskell - 循环图上的记忆遍历

问题描述

我有一个通常是循环的有向图，我想找到节点和接收器之间的关系。对有向图的遍历似乎非常适合递归记忆，因为该图可以映射到每个节点的遍历结果并进行查询，类似于规范的斐波那契记忆。但是，我发现检测循环会阻碍记忆工作，因为循环检测需要知道路径，并且可能有许多路径通向同一个节点，因此映射到图形的结果似乎取决于路径参数。但是，当循环被忽略时，结果实际上是明确的，但我看不出有任何方法可以将其传达给编译器。

作为一个简单但说明性的示例，假设我想找到从图中的节点可到达的所有接收器。DFS 的朴素算法看起来像这样：

import qualified Data.Set as Set

type AdjList = [[Int]]
adj :: AdjList
adj = ...
sinks :: Int -> [Int]
sinks = sinks' Set.empty where
  sinks' :: Set.Set Int -> Int -> [Int]
  sinks' path node | node `Set.member` path = [] -- this forms a cycle
                   | null (adj !! node) = [node] -- this is a sink
                   | otherwise = concatMap (sinks' (Set.insert node path)) (adj !! node)

而试图为记忆而写这个显然会在尝试填写路径参数时遇到问题：

sinks = sinks' Set.empty where
  sinks' path = (map (sinks'' {- what goes here? -}) [0..(length adj - 1)] !!) where
    sinks'' path' node | node `Set.member` path' = [] -- this forms a cycle
                       | null (adj !! node) = [node] -- this is a sink
                       | otherwise = concatMap (sinks' (Set.insert node path')) (adj !! node)

例如，在此图上的遍历中，我们可以看到从 A 到循环的路径有何不同，但如果节点 D 的结果被记忆，则遍历 D 只需执行一次：

我是否被迫使用显式表手动编写此备忘录？

标签： haskellmemoizationgraph-traversalcyclic-graph

解决方案

推荐阅读