3

假设你有一组人J，你需要为每个人拍一张照片。他们只有一位摄影师，摄影师有有限的时间T( |T|> |J|) 可用于拍摄每张照片。在任何给定时间，t摄影师T只能拍摄一张照片。中的每个人J只能在 中的某些时间段内拍摄他们的照片T，尽管每个人都被要求至少选择一次他们有空的时间。本质上，根据每个人的可用性，摄影师希望尝试将一个人分配到每个可用的时间段T这样每个人都可以拍照。有没有多项式时间算法来解决这个问题？如果不是，什么非多项式时间问题在多项式时间内简化为这个问题，即如何证明这个问题不在P?

例子：

摄影师有时可用[1, 12, 15, 33, 45, 77]。
人 A 有时有空[12, 33]。
B 人有时有空[1, 12]。
C 人有时有空[1, 12]。

我们可以通过以下选择拍摄每个人：
人 A：33
人 B：1
人 C：12

如果我们从选择 A: 12、 B:开始1，我们将无法找到 的位置C，即我们必须回溯并将 A 重新分配给33。

本质上，我正在寻找一种多项式时间算法来找到适当的时间分配（如果存在），否则能够报告不存在适当的分配。

4

2 回答 2

2

这可以建模为分配问题（或二分图匹配问题）。

来源应为人，目的地应为摄影师可用的时间。成本矩阵可以通过将一个人一次不可用的成本设为 1，可用性为 0 来构建。

如果矩阵不是方阵，则可以添加虚拟人，相应的成本为0。如果人数超过次数，则为不可能分配的情况。

如果最优解的最终成本不为零，则意味着分配是不可能的。

可以使用匈牙利算法在多项式时间内求解。

于 2013-12-07T06:57:24.800 回答
2

Abhishek 的回答将解决这个问题，但我想添加一个我发现更快的替代方案。Abhishek 已经（顺便提及）二分匹配，Hopcroft-Karp 算法与之相关。与匈牙利算法相比，Hopcroft-Karp 算法用于找到最大基数匹配并$O(sqrt(V)*E)$及时运行。O(n^3)“最大基数匹配”基本上意味着它找到可以进行的最大分配数量，因此在我之前的示例中，根据每个人的可用性和摄影师的可用时间段，可以为照片安排的最大人数。因此，如果返回的最大基数等于人数，您就知道每个人都可以进行分配。

请注意，我们可以在此示例中使用 Hopcroft-Karp 算法的原因是我们不关心边权重——只要每个人都有一些时间槽，谁被分配到哪个时间槽就没有区别。如果我们确实关心权重，我们将需要类似于匈牙利算法的东西，例如，如果我们有一个“不便因素”，每个人都分配给他们每个可用的时间段，因为匈牙利算法旨在优化这些条件下的结果，其中Hopcroft-Karp 只确定有多少分配是可能的。

在实践中，我开始使用匈牙利算法，在我的特定数据集上执行大约需要 30 秒。在将其切换为 Hopcroft-Karp 算法后，我可以在 < 1 秒内产生相同的结果。

于 2014-01-28T08:45:20.713 回答