采用与感兴趣节点的并集及其依赖项相交的整个图的拓扑排序。在伪代码中:
λ N = A ∩ (N ∪ D)
其中A是拓扑排序图的有序集, N是您关心的节点的子集,D是N的依赖关系。请注意,交集运算符必须遵守A的顺序。
或在 Haskell 中(如您的示例所示,使用数字代替字母作为节点):
import Data.List (intersect, union)
import Data.Graph (buildG, reachable, topSort)
graph = buildG (0, 4) [(3,2), (2,4), (2,1), (1,0)]
dependencies = buildG (0, 4) [(0, 1), (1, 2)]
ordering = topSort graph
f nodes = ordering `intersect` (nodes `union` deps)
where deps = concatMap (reachable dependencies) nodes
这假设您可以指定图形中的所有边。请注意,您只需要计算一次总排序,因此它应该在后续调用中具有高性能。
上面的代码将输出:
> f [0]
[2,1,0]
> f [0, 3]
[3,2,1,0]
> f [1, 3, 4]
[3,2,4,1]
与您的上述测试用例相匹配。
如果由于某种原因您不能指定图中的每条边,而只能指定相对约束,请按上述计算 (N ∪ D) 并应用约束满足。天真的方法是尝试这些节点的每一种排列,直到找到一个满足所有约束的排列。显然,即使是简单的深度优先和回溯方法,您也可以更有效地完成此操作。
编辑:深度优先代码
很简单。我们创建一棵我们关心的节点的所有排列的树,然后遍历/修剪该树,直到找到满足所有约束的排列(请注意,我们将依赖项附加到约束,因为依赖项也是约束)。所有约束都以 (A, B) 的形式指定,这意味着“A 必须在 B 之后”。
由于我们将排列生成为树而不是列表,因此只要给定的路径前缀违反约束,我们就可以轻松地修剪搜索空间的大块。
import Data.Maybe (fromMaybe, isJust)
import Data.List (union, nub, elemIndex, find)
import Data.Tree (unfoldTree, Tree (Node))
import Control.Applicative (liftA2)
dependencies = [(0, 1), (1, 2)]
constraints = [(2, 3), (4, 2)] ++ dependencies
f nodes = search $ permutationsTree $ (deps `union` nodes)
where deps = nub $ concatMap dependenciesOf nodes
search (Node path children)
| satisfies && null children = Just path
| satisfies = fromMaybe Nothing $ find isJust $ map search children
| otherwise = Nothing
where satisfies = all (isSatisfied path) constraints
constraints = constraintsFor path
constraintsFor xs = filter isApplicable constraints
where isApplicable (a, b) = (a `elem` xs) && (b `elem` xs)
isSatisfied path (a, b) = fromMaybe False $ liftA2 (>) i1 i2
where i1 = a `elemIndex` path
i2 = b `elemIndex` path
permutationsTree xs = unfoldTree next ([], xs)
where next (path, xs) = (path, map (appendTo path) (select xs))
appendTo path (a, b) = (path ++ [a], b)
select [] = []
select (x:xs) = (x, xs) : map (fmap (x:)) (select xs)
dependenciesOf x = nub $ x : concatMap dependenciesOf deps
where deps = map snd $ filter (\(a, b) -> a == x) dependencies
大部分代码都相当简单,但这里有一些我脑海中的笔记。
在计算上,这比之前发布的算法要昂贵得多。即使使用更复杂的约束求解器,您也不太可能做得更好(因为实际上没有任何预计算可以对这样的约束进行......至少没有一个对我来说是显而易见的)。
'f' 函数返回一个 Maybe,因为可能没有满足所有指定约束的路径。
constraintsFor约占总计算时间的 43%。这很天真。我们可以做一些事情来加速它:
1)一旦路径满足约束,向其附加节点不能使其违反该约束,但我们没有利用这一事实。相反,我们只是不断地重新测试给定路径的所有相关约束,即使已知约束之前已经通过。
2)我们对约束进行线性搜索以找到适用的约束。相反,如果我们将它们索引到它们适用的节点,我们可以加快速度。
3) 减少要测试的约束数量显然也会减少isSatisfied调用,这约占计算时间的 25%。
如果您要在严格执行的环境中实现这样的代码,则必须对代码结构进行一些修改。照原样,此代码在很大程度上依赖于惰性排列树,这使我们不必将搜索代码与树生成代码交织在一起,因为搜索代码根本不会走上它认为不合适的路径。
最后,如果您想找到所有解决方案,而不仅仅是第一个,只需将搜索正文更改为:
| satisfies && null children = [path]
| satisfies = concatMap search children
| otherwise = []
我没有花任何时间优化此代码或类似的东西,仅仅是因为假设您能够指定完整的图形(我相信您可以),原始算法显然更胜一筹。