预约调度算法（N人有N个自由闲插槽，约束满意度） [英] Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

问题描述

问题陈述

我们有一个老板想要采访N多人，因此使得ñ采访插槽。每个人都有自由在百忙之中为那些插槽。给出了一个算法，调度N多人分成N个插槽，如果可能的话，并返回一个标志/错误的/ etc，如果它是不可能的。什么是最快的运行时间复杂度？

我的方法，到目前为止

天真：有N个！方式来安排N多人。通过所有这些，对于每个排列，检查它是否可行。为O（n！）

回溯：

1. 查找，只能有1人的任何采访时隙。安排的人，从候选人名单中删除，并删除的插槽。
2. 查找任何考生只能进入1插槽。安排的人，从候选人名单中删除，并删除的插槽。
3. 在重复1安培; 2，直到没有更多的组合之类的。
4. 选择一个人，随机安排他们到他们的可用插槽之一。请记住这个操作。
5. 重复1，2，3，直到我们有一个时间表或有一个无法解决的冲突。如果我们有一个计划，将其返回。如果有一个无法解决的矛盾，原路返回。

这是O最坏的情况下，我认为（N！） - 这是没有任何好转。

有可能是一个D.P.解决方案，以及 - 但我没有看到它尚未

其他的想法

的问题可以被重新psented中的N×N矩阵，其中的行是槽，列是人$ P $，和的值是1为自由和0为忙。然后，我们正在寻找一个行列交换的身份矩阵这个矩阵中。步骤1和; 2正在寻找一个行或列只有一个1。 （如果矩阵的秩为= N，我这意味着有一个解决方案，但相反的不成立） 另一种方式来看待它是把矩阵作为unweighed向图边矩阵。然后，每个节点重新present 1候选和1个时隙。我们然后寻找一组边的，以便在图中每个节点具有一个出射边缘和一个进入边缘。或者，用2×节点，这将是一个二分图。

矩阵的例子：

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

解决方案

正如您所指出的，这个问题就相当于找到了二分图的最大匹配问题（一组顶点是一组人与其他的组时隙，有一个人，并且如果人可供该槽的槽）之间的边缘。

这个问题是可以解决的 Hopcroft - 卡普算法。

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

Problem statement

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?

My approaches so far

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

Backtracking:

1. Look for any interview time slots that can only have 1 person. Schedule the person, remove them from the list of candidates and remove the slot.
2. Look for any candidates that can only go into 1 slot. Schedule the person, remove them from the list of candidates and remove the slot.
3. Repeat 1 & 2 until there are no more combinations like that.
4. Pick a person, schedule them randomly into one of their available slots. Remember this operation.
5. Repeat 1, 2, 3 until we have a schedule or there is an unresolvable conflict. If we have a schedule, return it. If there's an unresolvable conflict, backtrack.

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

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

Other thoughts

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.

Example of a matrix:

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).

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

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

这篇关于预约调度算法（N人有N个自由闲插槽，约束满意度）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！