我业余学习算法,同意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)要分配。
我认为最好的方法可能是随机方法,因为理论上可以运行尽可能多的时间来获得结果。因此,以下是随机算法:
- 给定起始列和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行)。
前三个列:没有未分配的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分配给哪些组,以使不会创建新组(行),或者最少创建新组。我建议您运行“快速实现”和“随机”方法几次,并查看超出已知最小值的额外行数,如果数量很少的话。
id1 1, 1, 0, 0
和id2 1, 1, 0, 0
是否可以合并为1, 1, 0, 0 [id1&id2]
? - Allan Cameron