algorithm - 从选项列表中查找相互兼容的选项

Question

为了这个问题的目的，让我们为“OptionS”调用一个相互不兼容的选项列表。我有一个这样的 OptionS 列表，其中每个 Option 除了取消它自己的 OptionS 列表中的所有其他选项之外，还取消其他 OptionS 列表中的一些选项。这些规则是对称的，因此如果 A 禁止 B，则 B 禁止 A。

我想从每个列表中恰好选择一个选项，这样没有选项会相互取消资格。 Options(和 OptionS)太多，每一步中的取消资格太少，无法强制回溯解决方案。

它让人想起有点数独，但它不是一个精确的类比。从某些外部因素来看，我对不同的选项或至少有一个排序有一个粗略的可能性。

这个问题是否有更好的解决方案？是NP吗？

目前，我计划在解决方案空间中随机选择“路径”，按可能性加权。一种模拟退火。

编辑 - 澄清

• 我有一些向量，比方说在 5 到 500 之间。
• 每个向量包含 10 到 10000 个元素
• 每个元素排除了其他向量中的一些元素
• 这种关系是对称的
• 我想从每个向量中准确地挑选一个元素，并且没有元素相互排斥

如果没有办法从每个向量中选择一个，我想至少选择尽可能多的。数据的性质是这样的，总会有至少一个(最多几个)解决方案(或几乎是解决方案 - 只有少数遗漏)。

我不能分享真实数据，但一个例子是元素是 1 到 10e9 之间的整数，并且只允许成对总和超过 P 个质因数的元素。一些数字比其他数字更有可能“适合”其他数字，因为更大的数字往往有更多的因素，这使得一些选择更有可能像真实的那样。

根据需要选择 P 以及向量的大小和数量，使其具有适当的挑战性 :)。

我天真的解决方案:

• 我根据排除的其他元素的数量对元素进行排序，然后先尝试排除少数的元素(因为这样您就有更大的机会从每个元素中挑选一个)。
• 然后我根据“最佳”元素排除的元素数量对向量进行排序。排除了许多其他元素的向量是第一个。因此，首先尝试约束最多的向量，即使首先尝试该向量中约束最少的元素。
• 然后我首先搜索深度

这种方法的问题在于，如果第一个选择是错误的，那么深度优先搜索将永远没有时间到达下一个选择。

我在下面的评论中尝试解释的一种更好的方法是根据您选择的元素数量和剩余元素数量对元素的每个部分选择(搜索树中的节点)进行评分。然后我可以在每一步中更深入地查看得分最高的节点，这样第一个选择就不那么死板了。

一种类似的方法，我可能会首先尝试，因为它稍微容易一些，是进行模拟退火并采用随机路径，根据它们保留的可能性加权，沿着树向下。

Answer 1

根据允许的约束条件，我认为您可以将 SAT 降低到这个水平。

以 SAT 表达式为例(A|B|C)(~A|C|~D)...将 ~A 替换为 a 并从每个术语中生成一个向量，为您提供 {A,B,C} {a,C,d}...

您现在面临着从每个向量中选择一个元素的问题，受制于您不能选择变量的两个版本的约束 - 约束表明 A 与 a 不兼容，B 与 b 不兼容，依此类推。

如果您可以解决您的问题的这个实例，您可以通过将问题中选择为 A、B、C... 的真变量设置为选择为 a、b、c 的假变量来解决 SAT， .. 并为未选择的任何内容做出任意选择 - 因此您的问题至少与 SAT 一样难。 (除非你没有遇到这些限制，在这种情况下我没有证明你的问题有这么难)。

给定一个问题的实例，将一个变量与每个元素相关联，将约束写为 bool 表达式(通常只有 2 个变量)以给出看起来像 2-SAT 的东西，除了你需要为每个向量的表达式形式 (A|B|C|D|...) 表示您必须从每个向量中选择至少一个元素 - 因此您的问题的确切解决方案版本至少可以很好地编码为SAT 求解器 - 所以它在 NP 中，因为我们已经证明它是 NP 难的，所以它是 NP 完全的。