r - 优化(最小化)文件 : an optimization problem in line with permutations and agenda scheduling 中的行数

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)

约束条件如下:

个体数从500到1000不等，

序列的长度永远不会超过 30

文件中的每个序列都具有完全相同的长度，

算法需要在执行时间上合理，因为这个任务最多可能重复 200 次。

我们不需要寻找最优解，一个接近最优的解就足够了。

我们需要跟踪组合的个体(如上例所示)

遗传算法似乎是一个不错的选择，但它如何随着这个问题的规模(在执行时间方面)扩展？
中的建议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)要分配东西。
我认为最好的方法可能是随机方法，因为理论上您可以根据时间运行它多次以获得结果。所以这是随机算法:

给定起始列和 ID(上面的 1、4、5、8、9、12、16)。将此列和 ID 标记为已分配。

随机选择一个未分配的列(时间段)。如果你想要一个“更好”的结果。选择具有最少(或最多)数量未分配 ID 的那个。为了更快地实现，只需循环列。

随机选择一个未分配的 id。为了获得更好的结果，可能是可以分配该 ID 的组最多/最少的组。为了更快的实现，只需选择第一个未分配的 id。

查找所有可以分配未分配 ID 的组，而不会产生冲突。

将其随机分配给其中之一。为了更快地实现，只需选择第一个不会引起冲突的。如果没有没有冲突的组，则创建一个新组并将 id 分配给该组作为第一个 id。最佳结果是不必创建新组。

更新该行的数据(根据需要将 0 变为 1)。

重复步骤 3-5，直到该列没有未分配的 ID。

重复步骤 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是个体 (id) 的数量和 T是时隙数(列)。需要 O(NT)构建数据结构(基本上将表转换为图形)。之后，对于每一列，它最多需要检查和分配 O(N)个人 ID，他们可能会被检查多次。在实践中自 O(T)大约是 O(sqrt(N)) 并且性能随着您通过算法而增加(类似于快速排序)，很可能是 O(N log N)或 O(N sqrt(N))平均而言，虽然实际上使用 O(E) 可能更准确哪里 E是 1s的数量(边缘)在表中。每个都可能被检查和迭代固定次数。所以这可能是一个更好的指标。
NP 难点在于确定将哪些 id 分配给哪些组，以便不创建新组(行)或创建尽可能少的新组。我会运行“快速实现”和“随机”方法几次，看看你有多少额外的行(超出已知的最小值)，如果它是少量的话。