由于您尝试从两个维度解决此问题，并且除了上述问题之外，还针对其他问题，让我们探索一些更通用的解决方案。我们正在尝试解决有向图上的最短路径问题。
目前
a -> [a]，我们对图形的表示类似于，其中函数返回从输入可到达的顶点。另外，任何实现都需要我们进行比较以查看两个顶点是否相同，因此我们需要
Eqa。
下图是有问题的，并大致介绍了解决问题的几乎所有困难：
problematic 1 = [2]problematic 2 = [3]problematic 3 = [2]problematic 4 = []
当试图从1达到4时，必须检测到一个涉及2和3的循环，以确定没有从1到4的路径。
广度优先搜索
如果应用于有限图的一般问题，将提出的算法将具有在时间和空间上都不受限制的最坏情况下的性能。我们可以通过添加循环检测来修改他的解决方案，以解决仅包含有限路径和有限循环的图的一般问题。他的原始解决方案和此修改都将在无限图中找到有限路径，但都无法可靠地确定无限图中两个顶点之间没有路径。
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) tshortestPath :: (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个边的有限图。可以通过大小为n〜O（v +
e）的输入来描述具有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）））。
对于非有限的图形，这个功能应该只是不能确切地终止时不存在从有限的路径
i来
j但确实存在，从一个非限定路径
i来
j。
动态编程
动态编程解决方案不能以相同的方式推广。让我们探究原因。
首先，我们将采用chaosmasttter的解决方案，使其具有与广度优先搜索解决方案相同的界面：
instance Show Natural where show = show . tonuminfinity = Next infinityshortestPath' :: (Eq a) => (a->[a]) -> a -> a -> NaturalshortestPath' 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 -> NaturalfromInt x = (iterate Next Zero) !! xinstance Eq Natural where Zero == Zero = True (Next a) == (Next b) = a == b _ == _ = Falseinstance Ord Natural where compare Zero Zero = EQ compare Zero _ = LT compare _ Zero = GT compare (Next a) (Next b) = compare a b
我们可以问最短路径是否短于某个上限。我认为，这确实显示了惰性评估正在发生的情况。
problematic 1 4 < fromInt100是
False并且
problematic 1 4 > fromInt 100是
True。
接下来，要探索动态编程，我们将需要介绍一些动态编程。由于我们将为所有子问题建立一个解决方案表，因此我们需要知道顶点可以采用的可能值。这给我们一个稍微不同的界面：
shortestPath'' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> NaturalshortestPath'' 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 easierbuildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i ebuildTable bounds f = array bounds . map (x -> (x, f x)) $ range bounds
我们可以使用like
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 = []
如果我们试图从获取
1到
4，我们有两个选择：
- 去
2
和走的最短路径2
，以4
- 去
3
和走的最短路径3
，以4
如果我们选择探索
2，我们将面临以下选择：
- 去
3
和走的最短路径3
，以4
我们希望将从
3到的最短路径的两种探索结合
4到表中的同一条目中。如果我们想避免循环，那实际上是有些微妙的事情。我们面临的问题确实是：
- 去
2
，并采取从最短路径2
，以4
不参观1
- 去
3
，并采取从最短路径3
，以4
不参观1
选择之后
2
- 去
3
和走的最短路径3
，以4
不登陆1
或2
关于如何获得这两个问题
3，
4有两个略有不同的答案。它们是两个不同的子问题，它们不能放在表的同一位置。回答第一个问题最终需要确定你不能去
4的
2。回答第二个问题很简单。
我们可以为每个可能的先前访问的顶点集创建一堆表，但这听起来不是很有效。我几乎说服了我自己，仅靠懒惰就无法解决动态编程问题。
广度优先搜索Redux
在研究具有可达性或周期检测的动态编程解决方案时，我意识到，一旦我们看到了选项中的一个节点，无论我们是否跟随该节点，访问该节点的后续路径都永远不是最优的。如果我们重新考虑
problematic'：
如果我们试图从获取
1到
4，我们有两个选择：
- 去
2
，并采取从最短路径2
到4
无需访问1
，2
或3
- 去
3
，并采取从最短路径3
到4
无需访问1
，2
或3
这为我们提供了一种算法，可以很容易地找到最短路径的长度：
-- Vertices first reachable in each generationgenerations :: (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 novellengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe IntlengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i
不出所料，
lengthShortestPath (step 11) 4 5是
Just 3和
lengthShortestPathproblematic 1 4是
Nothing。
在最坏的情况下，
generations需要的空间为O（v * log v），时间为O（v * e * log v）。
