解决依赖性约束
我有一个经典的依赖性解决问题。 我以为我朝着正确的方向前进，但现在我遇到了障碍，我不知道该怎么办。
背景
在已知的Universe（所有工件的缓存及其依赖关系）中，每个工件和版本之间都存在1-> n关系，并且每个版本可能包含一组不同的依赖关系。 例如：
A 1.0.0 B (>= 0.0.0) 1.0.1 B (~> 0.1) B 0.1.0 1.0.0 给定一组“需求约束”，我想找到最好的解决方案（“最佳”是仍然满足所有约束的最高版本）。 以下是解决方案的“需求约束”示例：
solve!('A' => '~> 1.0') #=> {"A" => "1.0.1", "B" => "0.1.0"}
实际上，有更多的要求：
solve!('A' => '~> 1.0', 'B' => '>= 0.0.0', 'C' => '...', 'D' => '...')
（版本遵循语义版本标准）
我试过了
当前的解决方案使用回溯并且性能不高。 我做了一些挖掘，发现由于宇宙的大小导致了性能问题。 我决定尝试一种替代方法，并针对一组需求构建“可能性”DAG图：
class Graph def initialize @nodes = {} @edges = {} end def node(object) @nodes[object] ||= Set.new self end def edge(a, b) node(a) node(b) @nodes[a].add(b) self end def nodes @nodes.keys end def edges @nodes.values end def adjacencies(node) @nodes[node] end end
然后，我构建了一个来自宇宙的所有可能解决方案的DAG。 这大大减少了可能性的数量，并为我提供了具有真实工件可能性的实际图形。
def populate(artifact) return if loaded?(artifact) @graph.node(artifact) artifact.dependencies.each do |dependency| versions_for(dependency).each do |dependent_artifact| @graph.edge(artifact, dependent_artifact) populate(dependent_artifact) end end end private def versions_for(dependency) possibles = @universe.versions(dependency.name, dependency.constraint) # Short-circuit if there are no versions for this dependency, # since we know the graph won't be solvable. raise "No solution for #{dependency}!" if possibles.empty? possibles end
所以，从前面的示例图中，如果我有'A', '>= 0.0.0' ，我的DAG将如下所示：
+---------+ +---------+ | A-1.0.0 | | A-1.0.1 | +---------+ +---------+ / \ | / \ | / \ | / \ | +---------+ +---------+ | B-1.0.0 | | B-0.1.0 | +---------+ +---------+
由于A-1.0.0的可能值是“B的任何值”，但A-1.0.1的约束是“0.1系列中的任何B”。 这正在按预期工作（使用完整的测试套件）。
换句话说，DAG采用抽象依赖约束并创建一个“真实”图形，其中每个边缘是一个依赖项，每个顶点（我称之为node ）是一个实际的工件。 如果存在解决方案，则它位于此图中的某个位置。
可悲的是，这是我被卡住的地方。 我无法想出通过该图找到“最佳”路径的算法或程序。 我也不确定如何检测图表是否不可解决。
我做了一些研究，我认为拓扑排序（tsort）是我需要的过程。 但是，该算法确定依赖项的插入顺序，而不是最佳解决方案。
我很确定这是一个难以解决的问题，可能会有一个低效的运行时。 我虽然使用DAG会减少我必须做的比较次数。 这个假设我错了吗？ 是否有更好的数据结构可供使用？
最后的想法
- 我已将此问题标记为“Ruby”，因为我使用的是Ruby，但我正在寻找伪代码/方向。 这不是一个家庭作业问题 – 我真的想学习。
- 我试图尽可能多地提供背景，但如果您想了解特定主题的更多详细信息，请发表评论。 这已经很长了，但我确实有更多可以分享的代码。
我不是这个问题的专家，我提出的是一个不是最优的完整解决方案，因为有很多东西可以优化。
算法很简单，理想情况下是递归集。 交叉点DFS ：
算法
高清
Define: Name as String on format [ .* ] Define: Version as String on format [ dd.dd.dd ] Define: Revision as { Name, Version, Requirement } Define: Range as { min , max } Define: Condition as { Name, Range } Define: Requirement as Set OR as Set Define: Component as { Name, Range, Requirement } Define: System as Set
输入
Input: T as System aka basis Input: C as Set aka conditions to apply
初始化
Init: S as Set = { S[i] as Condition | S[i] = {T[i].Name,T[i].Range} } Init: Q as Stack = { push(q) | q[i] = C[i] }
处理
for (Condition c in C) { S.find(c.Name).apply(c) } While (Q.size > 0) { Condition q = Q.pop() switch (T.assert(S.find(q.Name),q)) { case VALID: S.find(q.Name).apply(q) q.push(S.find(q.Name).Requirement) case INVALID: S.find(q.Name).set(INVALID) case IDENTICAL: case SKIP: } } return S aka Solution
操作
Stack.push在堆栈的前面插入一个项目
Stack.pop从堆栈的前面删除一个项目
System.assert(Condition a, Condition b): if (a is INVALID) then return SKIP else if (b.Range = a.Range) then IDENTICAL else if (b.Range - a.Range = {}) then VALID else INVALID
Set.find(x)根据条件x搜索项目
Condition.apply(Condition b) = { this.Name, intersection(this.Range,b.Range) }