优化（最小化）文件中的行数：符合排列和议程调度的优化问题
Optimizing (minimizing) the number of lines in file: an optimization problem in line with permutations and agenda scheduling
我有一个日历，通常是一个包含多行的 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 是时隙数（列））基于贪心算法。
考虑约束规划方法。这是一个与您的问题非常相似的问题：.
一个非常简单的 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 段重叠）。找出图形的色数。然后每种颜色的顶点代表原始问题中的一条组合线。
图形着色是一个经过充分研究的问题，对于较大的实例，请考虑使用禁忌搜索或模拟退火的局部搜索方法。
我把学习算法作为一种爱好，我同意 Caduchon 的观点，贪婪是必经之路。虽然我认为这实际上是 clique cover 问题，但更准确地说：https://en.wikipedia.org/wiki/Clique_cover
可以在此处找到有关如何建立派系的一些想法：https://en.wikipedia.org/wiki/Clique_problem
团问题与独立集问题有关。
考虑到这些限制，而且我不熟悉 matlab 或 R，我建议：
第一步，构建独立集时隙数据。对于每个为 1 的时隙，创建所有也为 1 的记录的映射（用于快速查找）。 None 个可以合并到同一行（它们都需要合并到不同的行）。 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 不在该集合中。您也可以为此使用嵌套哈希 tables。 IE: 0: { id1: true, id2: true }`。集合还允许使用集合操作，这在确定未分配的 columns/ids.
时可能会有很大帮助
无论如何，这5个中的none个可以归为一组。这意味着充其量（给定该行）您必须至少有 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-complete 领域的地方，因为有大量（更准确地说，大约 2^N）要分配东西。
我认为最好的方法可能是随机方法，因为理论上您可以 运行 只要有时间就可以多次尝试以获得结果。所以这是随机算法：
- 给定起始列和 ID（上面的 1、4、5、8、9、12、16）。将此列和 ID 标记为已分配。
- 随机选择一个未分配的列（时间段）。如果你想要一个也许“更好”的结果。选择具有最少（或最多）数量未分配 ID 的那个。为了更快地实施，只需遍历列。
- 随机选择一个未分配的ID。为了获得更好的结果，也许可以为 most/least 组分配该 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是个体数（ids），T是时隙数（列）。构建数据结构需要 O(NT)（基本上是将 table 转换为图形）。之后，对于每一列，它最多需要检查和分配 O(N) 个单独的 ID，它们可能会被检查多次。在实践中，由于 O(T) 大致为 O(sqrt(N)) 并且随着算法的进行（类似于快速排序），性能会提高，因此平均而言可能 O(N log N) 或 O(N sqrt(N))，尽管实际上使用 O(E) 可能更准确，其中 E 是 table 中 1s（边）的数量。每一个都可能被检查并迭代固定次数。所以这可能是一个更好的指标。
NP 困难部分在计算将哪些 ID 分配给哪些组时发挥作用，以便不创建新组（行）或创建尽可能少的新组。我会运行“快速实施”和“随机”方法几次，看看你有多少额外的行（超过已知的最小值），如果它是少量的话。
这个问题，与一些评论相反，不是NP-complete，因为“一行中不能有两个分开的序列”的限制。这个限制意味着每条线都可以被认为代表一个区间。在这种情况下，问题减少到 a minimum coloring of an interval graph, which is known to be optimally solved via a greedy approach。即，根据结束时间按降序对间隔进行排序，然后按该顺序一次处理一个间隔，始终将每个间隔分配给与其不冲突的第一种颜色（即：合并线）或将其分配给如果新颜色与之前指定的所有颜色冲突，则使用新颜色。
我有一个日历，通常是一个包含多行的 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 是时隙数（列））基于贪心算法。
考虑约束规划方法。这是一个与您的问题非常相似的问题：
一个非常简单的 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 段重叠）。找出图形的色数。然后每种颜色的顶点代表原始问题中的一条组合线。
图形着色是一个经过充分研究的问题，对于较大的实例，请考虑使用禁忌搜索或模拟退火的局部搜索方法。
我把学习算法作为一种爱好，我同意 Caduchon 的观点，贪婪是必经之路。虽然我认为这实际上是 clique cover 问题，但更准确地说：https://en.wikipedia.org/wiki/Clique_cover
可以在此处找到有关如何建立派系的一些想法：https://en.wikipedia.org/wiki/Clique_problem
团问题与独立集问题有关。
考虑到这些限制，而且我不熟悉 matlab 或 R，我建议：
第一步，构建独立集时隙数据。对于每个为 1 的时隙，创建所有也为 1 的记录的映射（用于快速查找）。 None 个可以合并到同一行（它们都需要合并到不同的行）。 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 不在该集合中。您也可以为此使用嵌套哈希 tables。 IE: 0: { id1: true, id2: true }`。集合还允许使用集合操作，这在确定未分配的 columns/ids.
无论如何，这5个中的none个可以归为一组。这意味着充其量（给定该行）您必须至少有 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-complete 领域的地方，因为有大量（更准确地说，大约 2^N）要分配东西。
我认为最好的方法可能是随机方法，因为理论上您可以 运行 只要有时间就可以多次尝试以获得结果。所以这是随机算法：
- 给定起始列和 ID（上面的 1、4、5、8、9、12、16）。将此列和 ID 标记为已分配。
- 随机选择一个未分配的列（时间段）。如果你想要一个也许“更好”的结果。选择具有最少（或最多）数量未分配 ID 的那个。为了更快地实施，只需遍历列。
- 随机选择一个未分配的ID。为了获得更好的结果，也许可以为 most/least 组分配该 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是个体数（ids），T是时隙数（列）。构建数据结构需要 O(NT)（基本上是将 table 转换为图形）。之后，对于每一列，它最多需要检查和分配 O(N) 个单独的 ID，它们可能会被检查多次。在实践中，由于 O(T) 大致为 O(sqrt(N)) 并且随着算法的进行（类似于快速排序），性能会提高，因此平均而言可能 O(N log N) 或 O(N sqrt(N))，尽管实际上使用 O(E) 可能更准确，其中 E 是 table 中 1s（边）的数量。每一个都可能被检查并迭代固定次数。所以这可能是一个更好的指标。
NP 困难部分在计算将哪些 ID 分配给哪些组时发挥作用，以便不创建新组（行）或创建尽可能少的新组。我会运行“快速实施”和“随机”方法几次，看看你有多少额外的行（超过已知的最小值），如果它是少量的话。
这个问题，与一些评论相反，不是NP-complete，因为“一行中不能有两个分开的序列”的限制。这个限制意味着每条线都可以被认为代表一个区间。在这种情况下，问题减少到 a minimum coloring of an interval graph, which is known to be optimally solved via a greedy approach。即，根据结束时间按降序对间隔进行排序，然后按该顺序一次处理一个间隔，始终将每个间隔分配给与其不冲突的第一种颜色（即：合并线）或将其分配给如果新颜色与之前指定的所有颜色冲突，则使用新颜色。