优化（最小化）文件中行数：与排列和议程安排相一致的优化问题

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是时间段（列）的数量）。

- Grasshoper

---

在将其排成两行的示例中，您能解释一下为什么第二行（标记为id4）的最后四个条目是1、1、1、1吗？这是一个错误吗？ - Allan Cameron

另外，是否有可能合并和标记两个相同（重叠）的条目？例如，id1 1, 1, 0, 0 和 id2 1, 1, 0, 0 是否可以合并为 1, 1, 0, 0 [id1＆id2]？ - Allan Cameron

最后，结果必须填满1和0，还是可以使用ID标签？ - Allan Cameron

这似乎是最大覆盖问题的一个实例。这是一个NP难问题，因此您可能需要使用近似算法。我不认为遗传算法是一个好的选择... - Caduchon

实际上，集合覆盖是我主攻的课题。除非问题不是一般性问题，否则贪心算法是解决它的最佳多项式算法。如果你想要比贪心更好的解法，你就需要使用指数级算法复杂度。（当然，贪心算法在复杂度方面是最优秀的，但在这个世界上，O(10^17n²)比O(log(n)n²)更好......） - Caduchon

Answer 1

我业余学习算法，同意Caduchon的观点，贪心策略是可行的。尽管我认为这实际上是团覆盖问题，更准确地说：https://en.wikipedia.org/wiki/Clique_cover

有关如何构建团的一些思路可以在此处找到：https://en.wikipedia.org/wiki/Clique_problem

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

考虑到限制条件以及我不熟悉matlab或R，我建议采用以下步骤：

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

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不在该集合中。您还可以使用嵌套哈希表来实现。例如：0: {id1：true，id2：true}。集合也允许使用集合操作，在确定未分配的列/ID时可能会有所帮助。

无论如何，这五个人都不能组合在一起。这意味着在最好的情况下（考虑到该行），您必须至少有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）要分配。

我认为最好的方法可能是随机方法，因为理论上可以运行尽可能多的时间来获得结果。因此，以下是随机算法：

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行）。

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

第4列：将ID13分配给ID9组（13=>9）。现在，ID9看起来像这样，显示从ID9开始的组现在也包括ID13：

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

第五列: 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))，但实际上更准确的指标可能是使用E，其中E是表中1的数量（边缘）。每个边缘可能会被检查和迭代固定次数。因此，这可能是更好的指标。

NP难部分涉及解决将哪些id分配给哪些组，以使不会创建新组（行），或者最少创建新组。我建议您运行“快速实现”和“随机”方法几次，并查看超出已知最小值的额外行数，如果数量很少的话。

- Nuclearman

Answer 2

与某些评论相反，由于“一行中不能有两个分离的序列”的限制，该问题并非NP完全。这个限制意味着每一行可以被认为代表一个单一的区间。在这种情况下，该问题简化为区间图的最小染色问题，可以通过贪心算法来优化求解。具体而言，按照它们的结束时间降序对区间进行排序，然后依次处理这些区间，总是将每个区间分配给第一个不与其冲突的颜色（即：合并的行）或将其分配给新颜色，如果它与先前分配的所有颜色都冲突。

- mhum

---

哎呀，错过了那个要求。你是对的。它就不再是 NP 完全问题了。 - Nuclearman

Answer 3

考虑使用约束编程方法。这里有一个与您非常相似的问题：Constraint Programming: Scheduling with multiple workers。

一个非常简单的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段重叠），创建边。找到图的色数。然后，每种颜色的顶点表示原始问题中的一个组合行。

图着色是一个经过充分研究的问题，对于更大的实例，请考虑使用局部搜索方法，例如禁忌搜索或模拟退火。

- Magnus Åhlander

---

这里需要进行着色 - 这是非常研究透彻的方法，有许多现成的方法可以应用。 - David Eisenstat