一尘不染

预约调度算法(N个人有N个空闲时段,约束满足)

algorithm

问题陈述

我们有一个雇主想要采访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

阅读 597

收藏
2020-07-28

共1个答案

一尘不染

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

可以使用Hopcroft-
Karp算法
解决此问题。

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

2020-07-28