我有一个日历，通常是一个包含多行的csv文件。每一行对应于一个单独的值，并且是连续值"0"one_answers"1"的序列，其中"0"表示空时隙，"1"表示占用的时隙。一行中不能有两个分离的序列(例如两个由"0"(如"1,1,1,0,1,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基于Greedy算法在O(NT)(其中N是个体(id)的数量，T是时隙(列)的数量)中提供了一个工作解决方案。
我把研究算法作为一种爱好，在这一点上我同意Caduchon的观点，贪婪是我的出路。虽然我认为这实际上是集团掩护的问题，但更准确地说：https://en.wikipedia.org/wiki/Clique_cover
关于如何建立派系的一些想法可以在这里找到：https://en.wikipedia.org/wiki/Clique_problem
集团问题与独立集问题有关。
考虑到这些限制，而且我不熟悉matlab或R，我建议这样做：
步骤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。现在我们可以选择如何攻击事物。首先，我们选择个人最多的时段，并以此为起点。这给了我们尽可能少的行数。在这种情况下，我们实际上有一个平局，其中第二排和第五排都有7。我选择第二个，看起来像：
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分配给该组作为第一个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分配给哪些组时发挥作用，这样就不会创建新的组(行)或创建尽可能少的新组。我会运行"；快速实现"；以及"；"随机"；接近几次，看看你有多少额外的行(超过已知的最小值)，如果数量很小的话。
这个问题，与一些评论相反，由于限制"在一行中不能有两个分开的序列；。这一限制意味着每条线都可以被认为代表一个区间。在这种情况下，该问题减少到区间图的最小着色，已知通过贪婪方法可以最优解决。也就是说，根据间隔的结束时间按降序对间隔进行排序，然后按顺序一次处理一个间隔，始终将每个间隔分配给与其不冲突的第一种颜色(即：合并线)，或者如果它与之前分配的所有颜色冲突，则将其分配给新颜色。
考虑一种约束编程方法。这里有一个与您的问题非常相似的问题：约束编程：多个工人的调度。
一个非常简单的MiniZinc模型也可能看起来像(对不起，没有Matlab或R)：
include "globals.mzn";
%int: jobs = 4;
int: jobs = 16;
set of int: JOB = 1..jobs;
%array[JOB] of var int: start = [0, 6, 4, 0];
%array[JOB] of var int: duration = [3, 4, 1, 4];
array[JOB] of var int: start = [0, 6, 4, 0, 1, 8, 4, 0, 0, 6, 4, 1, 3, 9, 4, 1];
array[JOB] of var int: duration = [3, 4, 1, 5, 3, 2, 3, 4, 2, 2, 1, 3, 3, 1, 6, 8];
var int: machines;
constraint cumulative(start, duration, [1 | j in JOB], machines);
solve minimize machines;
然而，这个模型并不能说明在哪些机器上安排了哪些作业。
编辑：
另一种选择是将问题转化为图着色问题。让每条线都是图中的一个顶点。为所有重叠的线创建边(1段重叠)。求图的色数。然后，每种颜色的顶点表示原始问题中的组合线。
图着色是一个研究得很好的问题，对于较大的实例，请考虑使用禁忌搜索或模拟退火的局部搜索方法。