预约调度算法(N人有N个空闲-忙时隙，约束满足) [英] Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

问题描述

问题陈述

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

We have one employer that wants to interview N people, and therefore makes N interview slots. Every person has a free-busy schedule for those slots. Give an algorithm that schedules the N people into N slots if possible, and return a flag / error / etc if it is impossible. What is the fastest possible runtime complexity?

到目前为止我的方法

天真:有N个！安排N人的方法.遍历所有这些，对于每个排列，检查它是否可行.O(n!)

Naive: there are N! ways to schedule N people. Go through all of them, for each permutation, check if it's feasible. O( n! )

回溯:

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

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

This is O( n! ) worst case, I think - which isn't any better.

可能有一个 D.P.解决方案也是如此 - 但我还没有看到.

There might be a D.P. solution as well - but I'm not seeing it yet.

其他想法

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

The problem can be represented in an NxN matrix, where the rows are "slots", columns are "people", and the values are "1" for free and "0" for busy. Then, we're looking for a row-column-swapped Identity Matrix within this matrix. Steps 1 & 2 are looking for a row or a column with only one "1". (If the rank of the matrix is = N, I that means that there is a solution. But the opposite does not hold) Another way to look at it is to treat the matrix as an unweighed directed graph edge matrix. Then, the nodes each represent 1 candidate and 1 slot. We're then looking for a set of edges so that every node in the graph has one outgoing edge and one incoming edge. Or, with 2x nodes, it would be a bipartite graph.

矩阵示例:

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

推荐答案

正如你所指出的，这个问题等价于在二部图中寻找最大匹配的问题(一组顶点是人和槽集上的其他人，如果该人可用于该槽，则该人与该槽之间存在边).

As you pointed out, the problem is equivalent to the problem of finding a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).

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

This problem can be solved with the Hopcroft-Karp algorithm.

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

Complexity O(n^(5/2)) in the worst case, better if the graph is sparse.

这篇关于预约调度算法(N人有N个空闲-忙时隙，约束满足)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！