预约调度算法（N个人有N个空闲时段，约束满足）

  • Z时代
  • 2024-01-10
  • 分类：问答

我们有一个雇主想要采访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个时隙。然后，我们正在寻找一组边，以便图形中的每个节点都有一个输出边和一个输入边。或者，对于2x节点，它将是二部图。

矩阵示例：

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1

回答：

正如您所指出的那样，该问题等同于在二部图中找到最大匹配的问题（一组顶点是一组人，另一组是一组插槽，一个人与一个插槽之间存在一条边） （如果此人有空）。

可以使用Hopcroft-

Karp算法解决此问题。

复杂度O（n ^（5/2））在最坏的情况下，如果图形稀疏则更好。

以上是 预约调度算法（N个人有N个空闲时段，约束满足） 的全部内容， 来源链接： utcz.com/qa/419932.html

回到顶部