27

问题陈述

我们有一个雇主想要面试 N 个人，因此安排了 N 个面试名额。每个人都有这些时段的闲忙时间表。如果可能，请给出一个算法，将 N 人安排到 N 个插槽中，如果不可能，则返回标志 / 错误 / 等。最快的运行时复杂度是多少？

到目前为止我的方法

天真：有N个！安排N个人的方法。遍历所有这些，对于每个排列，检查它是否可行。在！ ）

回溯：

  1. 寻找任何只能有 1 人的面试时间段。安排此人，将其从候选人列表中删除并删除空档。
  2. 寻找任何只能进入 1 个位置的候选人。安排此人，将其从候选人列表中删除并删除空档。
  3. 重复 1 和 2，直到不再有类似的组合。
  4. 选择一个人，将他们随机安排到他们可用的位置之一。记住这个操作。
  5. 重复 1、2、3，直到我们有时间表或出现无法解决的冲突。如果我们有时间表，请将其退回。如果存在无法解决的冲突，请回溯。

这是 O(n!) 最坏的情况，我认为 - 这也好不到哪里去。

也可能有一个 DP 解决方案 - 但我还没有看到它。

其他想法

问题可以用 NxN 矩阵表示，其中行是“槽”，列是“人”，值为“1”表示空闲，“0”表示忙碌。然后，我们在这个矩阵中寻找一个行列交换的单位矩阵。步骤 1 和 2 正在寻找只有一个“1”的行或列。（如果矩阵的秩=N，则表示有解。但反之不成立）另一种看待它的方法是将矩阵视为未加权的有向图边矩阵。然后，每个节点代表 1 个候选和 1 个槽。然后，我们正在寻找一组边，以便图中的每个节点都有一条出边和一条入边。或者，如果有 2 个节点，它将是一个二分图。

矩阵示例：

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1
4

4 回答 4

13

正如您所指出的，该问题等效于在二分图中找到最大匹配的问题（一组顶点是人的集合，另一组在插槽集上，人和插槽之间有一条边如果此人有空）。

这个问题可以用Hopcroft-Karp 算法来解决。

最坏情况下的复杂度为 O(n^(5/2))，如果图稀疏则更好。

于 2012-06-21T18:12:41.627 回答
12

至于约束编程方法，它可以以不同的方式建模，例如使用矩阵方法和基于集合的方法。

下面以高级 CP 语言MiniZinc显示了基于集合的方法。s 是每个时间段可用的人（使用集合表示法）；决策变量是数组 x（每次应该分配给哪个人）。

包括“globals.mzn”；
整数：n = 4；

每个时段的空闲人数百分比
数组 [1..n] 的 int 集合：s =  
[{1,2,3,4},
 {2,3},
 {1,4},
 {1,4}];


% 决策变量
% 人员分配到一个位置（预约号 1..n）
var 1..n 的数组 [1..n]: x;

解决满足；

约束
  % 确保指定时间段的人员空闲
  forall(i in 1..n) (
    x[i] 在 s[i]
  )
  /\ % 确保每个人都有一个不同的时间段
  不同的（x）
;

输出[显示（x）]；

模型输出这 4 个解决方案（在 0.5 毫秒内），例如时间 1 分配给人员 3 等。

x: [3, 2, 4, 1]
----------
x: [2, 3, 4, 1]
----------
x: [3, 2, 1, 4]
----------
x: [2, 3, 1, 4]

MiniZinc 模型在这里：appointment_scheduling_set.mzn

矩阵方法模型在这里（没有输出部分）并使用标准整数编程方法：约会_调度.mzn 。

整数：n = 4；

% 行是时隙
% 列是人
int 的数组 [1..n, 1..n]：m = array2d(1..n, 1..n,
[
1, 1, 1, 1,
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
]);

% 决策变量
% 人员分配到一个位置（预约号 1..n）
var 0..1 的数组 [1..n, 1..n]: x;

解决满足；

约束
  forall(i in 1..n) (
    % 确保一个空闲槽
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1

    /\ % 确保每个位置和每个人分配一个
    sum([x[i,j] | j in 1..n]) = 1
    /\
    sum([x[j,i] | j in 1..n]) = 1
  )
;

该模型的解决方案是相同的，尽管以另一种（更冗长）的方式呈现，并且 - 碰巧 - 与基于集合的方法的顺序相同

插槽 1：3
插槽 2：2
插槽 3：4
插槽 4：1
----------
插槽 1：2
插槽 2：3
插槽 3：4
插槽 4：1
----------
插槽 1：3
插槽 2：2
插槽 3：1
插槽 4：4
----------
插槽 1：2
插槽 2：3
插槽 3：1
插槽 4：4
于 2012-06-21T18:38:15.640 回答
3

我相信你可以使用网络流。

  • u_i为候选者创建一个顶点i，v_j为槽创建一个顶点j。
  • 创建一个源节点s并将（有向）边从s每个u_i 容量 1 放置。
  • 制作一个汇节点t并从每个容量为 1 的v_jto放置一条边。t
  • 如果候选人可以在插槽中面试，则将优势从u_i到。v_jij
  • 我们有O(N)顶点和O(N^2)边，最大可能的流量是N。
  • 例如，使用Ford-Fulkerson 算法求最大流，O(E*f)其中E是边数，f是最大流的值，所以需要O(N^3)。
  • 如果最大流是N，那么我们有一个时间表：如果边缘有流 1，那么我们在 slot中(u_i,v_j)面试候选人，否则是不可能的。ij

根据积分流定理，最大流将在边上具有整数流，即 0 或 1，因此我们确实有一个有效的时间表。

于 2012-06-21T18:05:09.550 回答
3

这是最大二分匹配问题。

根据图的密度，最快的解决方案可能是Hopcroft-Karp 算法，它最多在 O(N^(5/2)) 时间内运行，但可能要快得多。

于 2012-06-21T18:14:28.677 回答