寻找尽可能多的配对

Question

寻找尽可能多的配对

4

我正在尝试解决一个问题，但不幸的是我的解决方案并不是最好的。

任务：

在一个聚会上，有N个客人（0 < N < 30000）。所有客人都会告诉你他们什么时候到达聚会，什么时候离开（例如[10;12]）。任务是在聚会上尽可能多地拍摄人物照片。一张照片上只能有2个人（一对），每个人只能出现在一张照片上。当然，只有当两个人的出席时间重叠时才能拍照。这种情况发生在他们的出席间隔重叠时。

我的想法：

我编写了一个程序，它从时间间隔创建连接图。从图中搜索具有最少连接数的人。从连接的人中，我还选择具有最少连接数的人。然后，这两者被选为一对照片。两者都从图中删除。该算法运行直到没有连接为止。

这种方法可以工作，但程序计算的时间限制为10秒。使用1000条数据，它需要2秒钟才能运行，但即使使用4000条数据，它也需要很长时间。此外，当我尝试使用25000条数据时，程序会因内存不足错误而停止，因此我甚至无法正确存储连接。

我认为这里需要一种新的方法，但我找不到其他方法使其正常工作。

有谁可以帮我找出这个任务的适当算法吗？

非常感谢！

示例数据：

第一行是客人数量，后续数据是派对上人数的间隔。

- stomseven

你需要一个精确的解决方案还是一个好的近似值？如果只需要一个近似值，可以尝试启发式算法，如模拟退火、遗传算法等。另一个问题：客人到达和离开的时间框架是什么？每个整点？任意的？ - Thomas

为什么不等到第一个离开的时间快到了，然后在那些在场的人中拍下即将离开的客人与下一个离开的人的合影呢？拍照需要时间吗？ - arne.b

是否可以同时拍摄两张照片？ - default locale

@arne.b 简单来说：当你拍摄一个仍在派对上的人时，你会让其他人失去与他配对的机会。而让人没有照片可能会带来你不想处理的不可预测的后果 ಠ_ಠ - default locale

2

@defaultlocale 是的，但是每个人只能与一个人配对，而离开的那个人需要立即拍照，那么选择配对可能性最少的伙伴有什么问题吗？ - arne.b

显示剩余3条评论

6个回答

2

看起来对我来说这是一个经典的最大匹配问题。

构建一个图，其中可以可能一起拍照的人（他们的时间间隔相交）通过边连接，然后找到最大匹配，例如使用Edmond's Blossom算法。

我不会说这很容易实现。但是，您可以使用Kuhn算法在二分图中找到最大匹配的相当好的近似解。这个算法非常容易实现，但不会给您精确的解决方案。

- dreamzor

1

这个想法不错，但我怀疑这不是最佳解决方案。Edmonds算法的时间复杂度为N^4，对于这个问题来说太高了。 - IVlad

@IVlad，这是“N的三次方”，而且你可以随时停止算法，使用启发式和其他我们所做的东西 :) - dreamzor

即使对于如此大的N，N^2 已经太多了。我怀疑提前停止这个算法并且仍然得到最优解并不足够好。 - IVlad

@IVlad实际上不会。对于30000的N^2，在中等配置的PC上运行几秒钟。重要的是要理解Edmond算法的渐近复杂度涵盖了最坏情况。如果你有一个随机图，那么目前它不是最坏情况。 - dreamzor

N^2对于30000不会通过在线评测，这似乎是来自在线评测系统。这些操作也很慢，涉及指针、动态分配等。在线评测机器通常速度较慢，而且它们通常具有良好的最坏情况测试。我非常确定这个算法不会通过测试。 - IVlad

1

我有一个非常简单的想法：

假设聚会需要X小时，每小时制作X组，并添加适当的人员。当然，比一个小时更长时间在那里的人将在几个组中。现在，如果有2组“一起”，有偶数人，您只需为每组拍摄n/2张照片。如果有2组奇数人，您正在寻找每个2组中的某个人，并将他移动到其中一个组中（因此，您得到了两组人数相同的人，在聚会上同时出现）。请记住删除所有已使用的人员（考虑一些类- Man，具有所有其/她小时列表）。

我的想法可能应该扩展到更先进的“移动人员”算法，通过多个相邻的集合。

- IProblemFactory

但这不会是24小时 - 例如看看92的离开时间。 - IVlad

好的，我会把24小时改成X，那么呢？ - IProblemFactory

然而，聚会的开始和结束时间可以分别从第一个到达时间和最后一个离开时间推断出来。这种方法可以在更一般的情况下进行适应。这里的真正假设是到达/离开时间是“充足”的小时数，根据OP显示的样本数据，这似乎是合理的。 - Rerito

如果X可以达到10 ^ 18，那么您的解决方案将不足够。我认为最佳方案不依赖于此。 - IVlad

此外，我认为这里展示的解决方案可能会导致“未解决”的情况，其中一些人离开派对时没有被拍照。 - Rerito

当然，“任务是在派对上尽可能多地拍摄人物照片。” - IProblemFactory

1

我认为以下方法可行：

首先，读取所有客人的数据，并按照离开时间升序将它们排序到一个数组中。然后，取出数组的第一个元素，并遍历下一个元素，直到找到第一个时间匹配（下一个客人的入场时间小于该客人的离开时间），如果找到，则将两者作为一对从数组中删除，并在其他地方报告。如果没有找到，则删除该客人，因为它根本无法配对。重复此操作，直到数组为空。

最坏情况下的时间复杂度也是N^2，因为派对可能像[1,2],[3,4],...这样，其中没有客人可以相互配对，算法将一直徒劳地搜索所有30000个客人。因此，我认为这不是最优算法，但它应该能给出确切的答案。

- Vesper

0

你说你已经有了一个图形结构表示。我假设你的顶点代表客人和他们在派对上逗留的时间段，边代表相应时间段的重叠。那么你需要解决的是图论中的最大匹配问题，这个问题以前已经被解决过。

然而，正如我在上面的评论中所指出的，我认为你可以利用问题的特性，特别是类似于传递性的“如果A在B之前离开，B在C到达之前离开，那么A和C也不会相遇”的特性，像这样：

等待下一个尚未拍照的客人即将离开，然后与在场的下一个离开的客人一起拍照。

- arne.b

我的一个问题是我无法创建包含25000个数据的图表。即使只有4000个数据，也需要4-7秒钟的时间，而我只有10秒钟来完成所有计算。25000个数据将会因为内存不足而失败。 - stomseven

@stomseven 我们不知道你的图有多密集，所以很难判断哪种表示或计算方法更有效。你也可以让Java使用更多的内存(-Xss200m -Xmx2000m或更高的值)。无论如何，你尝试过第二种方法吗？你只需要一个 class Guest { double comesAt, leavesAt; }(或者如果你想限制自己的话，可以用int)和两个按照第一/第二属性排序的列表，一个迭代递增的时间变量和一个 currentlyPresent 集合。 - arne.b

-1

你可能会想到拍摄照片的最早时间：那就是第二个人到达聚会的时候。

所以作为一名摄影师，要成为第一个到达聚会现场的人并等待。每当有人到达时，与他/她和聚会上所有其他人一起拍照。由于每个人只出现一次，你不会有任何重复的照片。

在拍照时（即遍历客人列表时），删除那些已经离开聚会的客人。

- alzaimar

2

你的“与他/她和派对上所有其他人一起拍照”的要求如何与“一个人只能在一张照片上”这个规定相符？ - arne.b

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- artahian · Accepted Answer

不需要在这里创建图表，这个问题可以很好地在区间结构上解决。按照他们的离开时间（区间结束点）升序排列人员。然后按照排序顺序迭代它们：如果当前人员与任何人员都没有交集，则应将其删除。如果他与多个人员相交，则选择其中一个离开时间最早的人员作为一对。在迭代过程中，您只需将每个人员与下一个人员进行比较即可。

证明这种方法并不困难，因此我希望你能自己证明它。关于运行时间，简单的解决方案将是O(N^2)，但我认为它可以缩短到O(N*logN)。无论如何，O(N^2)将适合普通PC上的10秒钟。