算法來解決版本範圍的依賴關係

Question

我有一個依賴關係算法的問題，依賴類似於maven依賴，除了它是基於嚴格的版本範圍。

例如：

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3 
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2 

現在，我想的依賴，當我想安裝組件A，版本1和成分d，第1版。因爲它們都依賴於組分B，C等我需要一個正確的算法來獲得B和C的正確版本

進一步，我可能需要升級組件A和D.例如，現在我有以下新版本：

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5 
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5 
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4 

現在我需要一種算法來獲得我可以升級到的A和D的正確版本及其所有依賴項。這裏的一個問題是成分A 3版本和組件d，第2版具有成分B的依賴性衝突

是否有現有的算法來解決這樣的問題呢？或類似（更容易）的問題。你有什麼建議嗎？

由於不應該有大量的數據，所以不考慮性能。

在此先感謝！

Answer 1

這是satisfiability problem的變體。 osgi也必須處理這個問題。所以你可以看看osgi規範和/或實現，看看它們是如何解決它的。

Answer 2

此問題是經由來自3SAT以下還原NP難題。給定一個3CNF公式，對於每個變量，都有一個包含兩個版本的組件，並且對於每個子句，都有一個包含三個版本的組件。我們想安裝一個版本的「超級」組件，它取決於所有的子組件，但對版本不挑剔。對於每個子句，子句組件1取決於出現在子句中的第一個變量，如果文字是正數，則需要版本1，如果是負數，則爲0。子句組件2取決於第二個變量等。我們可以安裝超級組件，當且僅當公式是可滿足的。

在這種減少的光，它是有道理的制定你的問題，因爲constraint satisfaction。每個組件都是一個變量，其可能的值是該組件的版本，如果沒有安裝該組件，則加上「未安裝」是一個選項。對於每個組件A的版本取決於組件B的版本，存在涉及A和B變量的約束，將版本的選擇限制爲其域的產品的特定子集。對於第一個例子中的A和B，這是{（1,1），（1,2），（1,3）}，因爲A版本1取決於B版本1〜3。如果A的版本2也可用，則這個約束將是{（1,1），（1,2），（1,3），（2,3），（2,4），（2,5） }。如果我們不必安裝A或B，那麼{（none，none），（none，1），（none，2），（none，3），（none，4），（none，5）， （1,1），（1,2），（1,3），（2,3），（2,4），（2,5）}。

由於您的情況是小，你可能需要一個完整的回溯搜索，可能與約束傳播。約束傳播的常用算法是AC-3，它強制實施弧一致性，即根據已被消除的內容從考慮中排除顯然無法工作的所有版本。例如，給定約束{（1,1），（1，2），（1,3）}，我們可以消除B =無，因爲從不出現。既然B的選擇是受限制的，那麼我們可以推斷B的依賴關係C等等。當沒有更多的簡化可以做時，我們必須猜測;一種策略是選擇剩下最少版本的組件並遞歸嘗試所有組件（回溯）。