由于您试图在两个维度上解决此问题，并且对于所描述的问题之外的其他问题，让我们探索一些更通用的解决方案。我们正在尝试解决有向图上的最短路径问题。
我们对图的表示目前类似于a -> [a]，其中函数返回从输入可到达的顶点。任何实现都需要我们可以比较两个顶点是否相同，所以我们需要Eq a.
下图是有问题的，并且介绍了一般解决问题的几乎所有困难：
problematic 1 = [2]
problematic 2 = [3]
problematic 3 = [2]
problematic 4 = []
当试图从 1 到达 4 时，必须检测到一个涉及 2 和 3 的循环，以确定没有从 1 到 4 的路径。
广度优先搜索
如果应用于有限图的一般问题，Will 提出的算法具有在时间和空间上都无界的最坏情况性能。我们可以修改他的解决方案，通过添加循环检测来解决仅包含有限路径和有限循环的图的一般问题。即使在无限图中，他的原始解决方案和此修改都将找到有限路径，但都无法可靠地确定无限图中的两个顶点之间没有路径。
acyclicPaths :: (Eq a) => (a->[a]) -> a -> a -> [[a]]
acyclicPaths steps i j = map (tail . reverse) . filter ((== j).head) $ queue
where
queue = [[i]] ++ gen 1 queue
gen d _ | d <= 0 = []
gen d (visited:t) = let r = filter ((flip notElem) visited) . steps . head $ visited
in map (:visited) r ++ gen (d+length r-1) t
shortestPath :: (Eq a) => (a->[a]) -> a -> a -> Maybe [a]
shortestPath succs i j = listToMaybe (acyclicPaths succs i j)
重用stepWill 的答案中的函数作为示例问题的定义，我们可以得到从 11 层建筑的 4 层到 5 层的最短路径长度fmap length $ shortestPath (step 11) 4 5。这返回Just 3。
让我们考虑一个有 v 个顶点和 e 个边的有限图。具有 v 个顶点和 e 个边的图可以用大小为 n ~ O(v+e) 的输入来描述。该算法的最坏情况图是有一个无法到达的顶点 ，j而剩余的顶点和边专门用于创建从 开始的最大数量的非循环路径i。这可能类似于一个包含所有非i或的顶点的集团j，其边缘从i到非 的所有其他顶点j。具有 e 条边的团的顶点数为 O(e^(1/2))，因此该图有 e ~ O(n)，v ~ O(n^(1/2))。在确定j无法访问之前，该图将有 O((n^(1/2))!) 路径可供探索。
在这种情况下，此函数所需的内存为 O((n^(1/2))!)，因为它只需要在每个路径的队列中不断增加。
在这种情况下，此函数所需的时间是 O((n^(1/2))! * n^(1/2))。每次扩展路径时，它必须检查新节点是否已经在路径中，这需要 O(v) ~ O(n^(1/2)) 时间。如果我们拥有Ord a并使用Set a类似的结构来存储访问过的顶点，则可以将其改进为 O(log (n^(1/2)))。
对于非有限图，只有在不存在 from to 的有限路径但确实存在 from ito的j非有限路径时，此函数才应准确终止。ij
动态规划
动态规划解决方案的泛化方式不同。让我们探讨一下原因。
首先，我们将调整 chaosmasttter 的解决方案，使其具有与广度优先搜索解决方案相同的界面：
instance Show Natural where
show = show . toNum
infinity = Next infinity
shortestPath' :: (Eq a) => (a->[a]) -> a -> a -> Natural
shortestPath' steps i j = go i
where
go i | i == j = Zero
| otherwise = Next . foldr minimal infinity . map go . steps $ i
这很好地解决了电梯问题，shortestPath' (step 11) 4 5是3。不幸的是，对于我们有问题的问题，shortestPath' problematic 1 4堆栈溢出。如果我们为数字添加更多代码Natural：
fromInt :: Int -> Natural
fromInt x = (iterate Next Zero) !! x
instance Eq Natural where
Zero == Zero = True
(Next a) == (Next b) = a == b
_ == _ = False
instance Ord Natural where
compare Zero Zero = EQ
compare Zero _ = LT
compare _ Zero = GT
compare (Next a) (Next b) = compare a b
我们可以询问最短路径是否短于某个上限。在我看来，这确实展示了惰性评估正在发生的事情。problematic 1 4 < fromInt 100是False和problematic 1 4 > fromInt 100是True。
接下来，为了探索动态规划，我们需要介绍一些动态规划。由于我们将构建所有子问题的解决方案表，因此我们需要知道顶点可以采用的可能值。这给了我们一个稍微不同的界面：
shortestPath'' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> Natural
shortestPath'' steps bounds i j = go i
where
go i = lookupTable ! i
lookupTable = buildTable bounds go2
go2 i | i == j = Zero
| otherwise = Next . foldr minimal infinity . map go . steps $ i
-- A utility function that makes memoizing things easier
buildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i e
buildTable bounds f = array bounds . map (\x -> (x, f x)) $ range bounds
我们可以像shortestPath'' (step 11) (1,11) 4 5或一样使用它shortestPath'' problematic (1,4) 1 4 < fromInt 100。这仍然无法检测周期...
动态编程和循环检测
循环检测对于动态规划来说是有问题的，因为当从不同的路径接近子问题时，它们是不一样的。考虑我们problematic问题的一个变体。
problematic' 1 = [2, 3]
problematic' 2 = [3]
problematic' 3 = [2]
problematic' 4 = []
如果我们试图从1to 4，我们有两个选择：
- go to并采取从to 到
2的最短路径24
- go to并采取从to 到
3的最短路径34
如果我们选择探索2，我们将面临以下选择：
我们希望将最短路径的两个探索组合3到4表中的同一个条目中。如果我们想避免循环，这确实有点微妙。我们真正面临的问题是：
- go to
2并采取最短路径 from 2to 4that don't visit1
- go to
3并采取最短路径 from 3to 4that don't visit1
选择后2
这两个关于如何得到的问题3有4两个略有不同的答案。它们是两个不同的子问题，不能放在表中的同一位置。回答第一个问题最终需要确定您无法4从 from获得2。回答第二个问题很简单。
我们可以为每个可能的先前访问过的顶点集制作一堆表格，但这听起来效率不高。我几乎已经说服自己，我们不能仅使用惰性来将可达性作为一个动态编程问题。
广度优先搜索
在研究具有可达性或循环检测的动态规划解决方案时，我意识到一旦我们在选项中看到了一个节点，无论我们是否遵循该节点，以后访问该节点的路径都不会是最优的。如果我们重新考虑problematic'：
如果我们试图从1to 4，我们有两个选择：
- go to并采取从to
2的最短路径而不访问, , 或24123
- go to并采取从to
3的最短路径而不访问, , 或34123
这为我们提供了一种算法，可以很容易地找到最短路径的长度：
-- Vertices first reachable in each generation
generations :: (Ord a) => (a->[a]) -> a -> [Set.Set a]
generations steps i = takeWhile (not . Set.null) $ Set.singleton i: go (Set.singleton i) (Set.singleton i)
where go seen previouslyNovel = let reachable = Set.fromList (Set.toList previouslyNovel >>= steps)
novel = reachable `Set.difference` seen
nowSeen = reachable `Set.union` seen
in novel:go nowSeen novel
lengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe Int
lengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i
正如所料，lengthShortestPath (step 11) 4 5isJust 3和lengthShortestPath problematic 1 4is Nothing。
在最坏的情况下，generations需要 O(v*log v) 的空间和 O(v*e*log v) 的时间。
