优化（最小化）文件中的行数：符合排列和议程调度的优化问题

Question

我有一个日历，通常是一个包含多行的 csv 文件。每行对应一个个体，是一个连续值“0”和“1”的序列，其中“0”表示空时隙，“1”表示占用时隙。一行中不能有两个分隔的序列（例如，两个由“0”分隔的“1”序列，例如“1,1,1,0,1,1,1,1”）。

问题是通过组合个体并解决时隙之间的冲突来最小化行数。注意时隙不能重叠。例如，对于 4 个个体，我们有以下序列：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,0,0,0,0,0,0

可以将它们排列成两行，同时跟踪排列的个人（记录）。在我们的例子中，它产生：

1,1,1,0,1,0,1,1,1,1 (id1 + id2 + id3)
1,1,1,1,0,0,0,0,0,0 (id4)

约束条件如下：

1. 人数从500到1000不等，
2. 序列的长度永远不会超过30
3. 文件中的每个序列都具有完全相同的长度，
4. 算法需要在执行时间上合理，因为这个任务最多可能重复 200 次。
5. 我们不需要寻找最优解，一个接近最优的解就足够了。
6. 我们需要跟踪组合的个体（如上例所示）

遗传算法似乎是一个不错的选择，但它如何随着这个问题的规模（在执行时间方面）扩展？

Matlab或R 中的建议将（非常）感谢。

这是一个示例测试：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,1,0,0,0,0,0
id5:0,1,1,1,0,0,0,0,0,0
id6:0,0,0,0,0,0,0,1,1,1
id7:0,0,0,0,1,1,1,0,0,0
id8:1,1,1,1,0,0,0,0,0,0
id9:1,1,0,0,0,0,0,0,0,0
id10:0,0,0,0,0,0,1,1,0,0
id11:0,0,0,0,1,0,0,0,0,0
id12:0,1,1,1,0,0,0,0,0,0
id13:0,0,0,1,1,1,0,0,0,0
id14:0,0,0,0,0,0,0,0,0,1
id15:0,0,0,0,1,1,1,1,1,1
id16:1,1,1,1,1,1,1,1,0,0

解决方案

@Nuclearman 提供了一个基于贪婪算法的工作解决方案O(NT)（其中N是个体（id）T的数量，是时隙（列）的数量）。

Answer 1

我将算法作为一种爱好学习，我同意 Caduchon 的观点，贪婪是必经之路。虽然我认为这实际上是集团封面问题，但更准确地说：https : //en.wikipedia.org/wiki/Clique_cover

可以在此处找到有关如何建立集团的一些想法：https : //en.wikipedia.org/wiki/Clique_problem

集团问题与独立集问题有关。

考虑到限制，而且我不熟悉 matlab 或 R，我建议这样做：

Step 1. 建立独立集时隙数据。对于每个为 1 的时隙，为所有也为 1 的记录创建一个映射（用于快速查找）。这些都不能合并到同一行中（它们都需要合并到不同的行中）。IE：对于第一列（槽），数据的子集如下所示：

id1 :1,1,1,0,0,0,0,0,0,0
id4 :1,1,1,1,1,0,0,0,0,0
id8 :1,1,1,1,0,0,0,0,0,0
id9 :1,1,0,0,0,0,0,0,0,0
id16:1,1,1,1,1,1,1,1,0,0

数据将存储为类似0: Set(id1,id4,id8,id9,id16)（零索引行，我们从第 0 行而不是第 1 行开始，尽管在这里可能无关紧要）。这里的想法是进行 O(1) 查找。您可能需要快速告诉 id2 不在该集合中。您也可以为此使用嵌套哈希表。IE: 0: { id1: true, id2: true }`。集合还允许使用集合操作，这在确定未分配的列/id 时可能会有很大帮助。

在任何情况下，这 5 个都不能归为一组。这意味着最多（给定该行）您必须至少有 5 行（如果其他行可以合并到 5 行而不会发生冲突）。

这一步的性能是 O(NT)，其中 N 是个体数，T 是时隙数。

第 2 步。现在我们可以选择如何攻击事物。首先，我们选择人数最多的时间段，并将其作为我们的起点。这给了我们最小可能的行数。在这种情况下，我们实际上有一个平局，其中第 2 行和第 5 行都有 7。我要使用第 2 行，它看起来像：

id1 :1,1,1,0,0,0,0,0,0,0
id4 :1,1,1,1,1,0,0,0,0,0
id5 :0,1,1,1,0,0,0,0,0,0
id8 :1,1,1,1,0,0,0,0,0,0
id9 :1,1,0,0,0,0,0,0,0,0
id12:0,1,1,1,0,0,0,0,0,0
id16:1,1,1,1,1,1,1,1,0,0

步骤 3. 现在我们有了起始组，我们需要添加到它们中，同时尽量避免新成员和旧组成员之间的冲突（这需要额外的一行）。这是我们进入 NP 完全领域的地方，因为有很多东西（更准确地说大约是 2^N）要分配东西。

我认为最好的方法可能是随机方法，因为理论上您可以根据时间运行它多次以获得结果。所以这是随机算法：

1. 给定起始列和 ID（上面的 1、4、5、8、9、12、16）。将此列和 ID 标记为已分配。
2. 随机选择一个未分配的列（时间段）。如果你想要一个“更好”的结果。选择具有最少（或最多）数量未分配 ID 的那个。为了更快地实现，只需循环列。
3. 随机选择一个未分配的 id。为了获得更好的结果，可能是可以分配该 ID 的组最多/最少的组。为了更快的实现，只需选择第一个未分配的 id。
4. 查找所有可以分配未分配 ID 的组，而不会产生冲突。
5. 将其随机分配给其中之一。为了更快地实现，只需选择第一个不会引起冲突的。如果没有没有冲突的组，则创建一个新组并将 id 分配给该组作为第一个 id。最佳结果是不必创建新组。
6. 更新该行的数据（根据需要将 0 变为 1）。
7. 重复步骤 3-5，直到该列没有未分配的 ID。
8. 重复步骤 2-6，直到没有未分配的列剩余。

使用更快实现方法的示例，这是一个最佳结果（不能少于 7 行，结果中只有 7 行）。

前 3 列：没有未分配的 ID（全部为 0）。跳过。

第 4 列：将 id13 分配给 id9 组（13=>9）。id9 现在看起来像这样，表明以 id9 开头的组现在还包括 id13：

id9 :1,1,0,1,1,1,0,0,0,0 (+id13)

第 5 列：3=>1、7=>5、11=>8、15=>12

现在它看起来像：

id1 :1,1,1,0,1,0,0,0,0,0 (+id3)
id4 :1,1,1,1,1,0,0,0,0,0
id5 :0,1,1,1,1,1,1,0,0,0 (+id7)
id8 :1,1,1,1,1,0,0,0,0,0 (+id11)
id9 :1,1,0,1,1,1,0,0,0,0 (+id13)
id12:0,1,1,1,1,1,1,1,1,1 (+id15)
id16:1,1,1,1,1,1,1,1,0,0

我们将快速查看下一列并查看最终结果：

7th Column: 2=>1, 10=>4
8th column: 6=>5
Last column: 14=>4

所以最后的结果是：

id1 :1,1,1,0,1,0,1,1,1,1 (+id3,id2)
id4 :1,1,1,1,1,0,1,1,0,1 (+id10,id14)
id5 :0,1,1,1,1,1,1,1,1,1 (+id7,id6)
id8 :1,1,1,1,1,0,0,0,0,0 (+id11)
id9 :1,1,0,1,1,1,0,0,0,0 (+id13)
id12:0,1,1,1,1,1,1,1,1,1 (+id15)
id16:1,1,1,1,1,1,1,1,0,0

方便的是，即使是这种“简单”的方法也允许我们将剩余的 id 分配给原始的 7 个组，而不会发生冲突。这在实践中不太可能发生，如您所说的“500-1000”ID 和多达 30 列，但远非不可能。粗略地说，500 / 30 大约是 17，而 1000 / 30 大约是 34。所以我希望你能够减少到大约 10-60 行，大约有 15-45 行，但它高度依赖于数据和有点运气。

理论上，这个方法的性能是O(NT)哪里N是个体数（ids），T是时隙数（列）。它需要O(NT)构建数据结构（基本上将表转换为图形）。之后，对于每一列，它最多需要检查和分配O(N)单个 id，它们可能会被检查多次。在实践中，因为O(T)大约是 O(sqrt(N)) 并且性能随着您通过算法而增加（类似于快速排序），它很可能O(N log N)或O(N sqrt(N))平均，尽管实际上使用O(E)whereE的数量可能更准确1s（边缘）在表中。每个都可能被检查和迭代固定次数。所以这可能是一个更好的指标。

NP 难点在于确定将哪些 id 分配给哪些组，以便不创建新组（行）或创建尽可能少的新组。我会运行“快速实现”和“随机”方法几次，看看你有多少额外的行（超出已知的最小值），如果它是少量的话。

Answer 2

与某些评论相反，由于“一行中不能有两个分开的序列”的限制，这个问题不是 NP 完全的。这个限制意味着每条线都可以被认为代表一个间隔。在这种情况下，问题简化为区间图的最小着色，已知可以通过贪心方法最佳地解决该问题。即，根据它们的结束时间按降序对间隔进行排序，然后按该顺序一次处理一个间隔，始终将每个间隔分配给它不冲突的第一种颜色（即：合并线）或将其分配给如果它与所有先前分配的颜色冲突，则使用新颜色。