algorithm - 什么算法可以用备选方案分析依赖关系？

Question

我有一组相互依赖的元素。这些依赖关系可能是严格的，例如。a取决于b和c; 或者某些元素可能有替代品，例如。s取决于t或u。没有循环依赖。

我正在尝试对依赖信息做两件事：

（事实上 2 在给定 1 的情况下是微不足道的，因为我可以在资源允许的情况下生成所有排列并检查它们。不过可能有更好的算法。）

是否有适用于具有替代依赖项的元素的算法？我发现很多只考虑严格依赖关系，但我不知道足够的术语来缩小我的搜索范围。

score 1 · Accepted Answer

假设您的元素列在L中。然后，对于L中的每个元素e，您验证所有直接依赖关系都已解决。要验证每个元素e，您可以遍历e的依赖项列表D并确保D中的所有元素d都在L中找到。为了解决替代方案的情况，现在将每个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_ds。您可以预先生成这些索引，因为您知道L的每个元素的备选数量。您可以在 MATLAB 中签出ndgrid，如以下代码所示，假设元素a具有三个依赖项，而b具有两个：

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

有关如何使用此类预计算索引的参考，与您要实现的语言无关。

score 0 · Accepted Answer

对于非严格依赖，如果它只有两个选择，例如。s 取决于 t 或 u（不再），您可以将其视为2SAT-problem并解决它。

2 回答 2