algorithm - AI - PSO - 选择正确的表示

Question

假设我有一个包含 N 个自然数的集合 S 和该集合的 N 个子集(S1、S2、...Sn)。我想生成 2 个子集 D1 和 D2(D1 + D2 = S，D1 和 D2 没有公共(public)元素)以便 D1 和 D2 不包含任何这 N 个子集。

简单示例:

S = 1 2 3 4 5

S1 = 1 4

S2 = 1 2

S3 = 1 2 3

S4 = 1 2 3 4

S5 = 1 2 4

D1 = 1 3 5

D2 = 2 4

我的第一个想法是，粒子所占据的位置将描述元素的选择方式(假设位置是一个包含 N BYTE 元素的数组，如果 position[i] 为 1，则 Set[i] 在 D1 中， 2 在 D2 中，以使其简单)。

解决方案的适应度可以是 N - 解决方案中包含的初始子集的数量。

但是速度是多少？我无法弄清楚这部分的事实让我觉得也许我需要用另一种方式来表示这个位置，但同样，我找不到会使情况过于复杂的东西。

我对理论答案更感兴趣。我应该用什么方式表示数据以及为什么。

我是这个 PSO 的新手，所以任何关于这个主题的好读物(初学者水平)都会受到赞赏。

Answer 1

正如 amit 所建议的那样，这实际上是一个 NP-hard 问题。给定一个 CNF 公式，让 S 与所有文字(正和负)的集合加上一对额外的 T 和 F 一一对应。做一个集合 {T, F}。为每个变量创建一个双元素集合，其中包含该变量的正负文字，以便一个与 T 共享一个集合，另一个与 F 共享一个集合。对于析取的每个子句，创建一个包含其文字和 F 的集合。 CNF-SAT 实例的解和这个问题的实例是一一对应的，通过为与 T 共享集合的所有文字分配 true。

如果你想解决这个问题，我建议使用 SAT 求解器，因为用 CNF 表达它并不难。如果您想了解粒子群优化，我会建议一个不同的问题，具有连续的解决方案空间。