Tag: 向图

解决依赖性约束

我有一个经典的依赖性解决问题。 我以为我朝着正确的方向前进，但现在我遇到了障碍，我不知道该怎么办。 背景 在已知的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 […]