我是一位有用的助手，可以为您翻译文本。
我遇到了一个典型的依赖关系解决问题。我以为我朝着正确的方向前进，但现在我遇到了障碍，不确定如何继续下去。
背景
在已知的宇宙（所有工件及其依赖项的缓存）中，每个工件和版本之间存在1对n的关系，每个版本可能包含不同的依赖项。例如：
我遇到了一个典型的依赖关系解决问题。我以为我朝着正确的方向前进，但现在我遇到了障碍，不确定如何继续下去。
背景
在已知的宇宙（所有工件及其依赖项的缓存）中，每个工件和版本之间存在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获取抽象依赖约束并创建一个“真实”的图，其中每条边都是一个依赖关系，每个顶点（我称之为节点）都是一个实际的构件。如果存在解决方案，则它在这个图中的某个地方。
遗憾的是，这就是我卡住的地方。我无法想出一种算法或过程来找到通过这个图的“最佳”路径。我也不确定如何检测图是否可解。
我做了一些研究，我认为拓扑排序（tsort）是我所需要的过程。然而，该算法确定依赖项的插入顺序，而不是最佳解决方案。
我相当确定这是一个np-hard问题，并且可能具有低效的运行时间。我认为使用DAG会减少我必须进行的比较次数。我的假设错了吗？有更好的数据结构可以使用吗？
最终思考
- 我将此问题标记为“Ruby”，因为我正在使用Ruby，但我正在寻找伪代码/方向。这不是一个家庭作业问题-我真的在努力学习。
- 我尽可能地提供了尽可能多的背景信息，但如果您需要特定主题的更多细节，请留下评论。这已经是一篇冗长的文章，但我还有更多的代码可以分享。