0

假设我有一个包含 N 个自然数的集合 S 和该集合的 N 个子集（S1，S2，...Sn）。我想生成 2 个子集 D1 和 D2（D1 + D2 = S，D1 和 D2 没有公共元素），以便 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 的新手，所以任何关于这个主题的好读物（初级）都会受到赞赏。

4

1 回答 1

1

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

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

于 2015-05-07T12:02:03.523 回答