什麼算法可以分析依賴關係？

Question

我有一組元素，彼此之間有各種依賴關係。這些依賴可能是嚴格的，例如。 a取決於b和c;或者某些元素可能有其他選擇，例如。 s取決於t或u。沒有循環依賴關係。

我試圖做兩件事情與依賴信息：

1. 確定一組給定的元素是否具有所有依賴性解決
2. 列出所有可能的徹底解決一組元素

（其實2瑣碎給出1，因爲我可以生成所有排列，並檢查他們，在資源允許的。可能有更好的算法，雖然。）

有沒有這樣的算法適應具有替代依賴關係的元素？我發現很多隻能說明嚴格的依賴關係，但我不知道足夠的術語來縮小搜索範圍。

Answer 1

讓我們假設你的元素在大號上市。然後，對於大號每個元素Ë您驗證所有直接依賴性都解決了。爲了驗證每一個元素Ë，你可以通過列表d走的è的依賴關係，並確保所有元素d在d在大號被發現。爲了解決替代方案的情況，現在將每個d想象爲其自己的替代依賴項列表。

for each d in e.D 
    d_ok = false 
    for each alt_d in d 
     if alt_d in L: d_ok = true, break 
    if not d_ok: return false 
return true 

要列出滿足您的依賴所有可能的集合，你可以使用置換索引通過所有alt_d S IN的所有可能的不同的順序進行迭代。您可以事先生成這些索引，因爲您知道L的每個元素的替代數量。你可以在MATLAB退房ndgrid作爲在下面的代碼，假設有元素一個有三個依賴和b有兩個：

[idx_a, idx_b] = ndgrid(1:3, 1:2); 
idx = [idx_a(:), idx_b(:)]; 

關於如何使用這些預先計算的指數基準，獨立語言要實現這一點。

Answer 2

非嚴格的依賴關係，如果它只有兩種選擇，例如。 s取決於t或u（不再），你可以把它看作2SAT-problem並解決它。