最佳的面试安排算法

huangapple go评论65阅读模式
英文:

Best algorithm for scheduling interviews

问题

Sure, here's the translated content:

我想考虑一种最佳算法,让面试官与尽可能多的候选人会面。

假设有n名候选人和一名面试官。每次面试都将在固定时间内进行,因此我们可以将每次面试视为占用一个时间段。时间段的数量为m。所有候选人都被要求提交他们是否在每个时间段都可用。

如果我将其以表格形式呈现,看起来像这样。

1:可用
0:不可用

         Aoi   Banri  ...   Nami
时间段1    1      1    ...    0
时间段2    0      1    ...    1
 .        .      .    .      .
 .        .      .     .     .
 .        .      .      .    .
时间段m    0      1    ...    0
  • 可能的方法1:将其视为矩阵问题来解决

如果我将这个问题视为矩阵问题,那么它将被简化为找到矩阵X,表示为只有一对一列交换的矩阵的乘积,以最大化trace(AXI)。其中A是日程表,I是单位矩阵。

有没有什么好方法可以做到这一点?

  • 可能的方法2:将其视为算法问题来解决

如果有人能够考虑出一种总是产生最佳结果的最佳算法,那不一定是一个矩阵问题。我想到的一种方法可能是:

  1. 找到具有最少可用时间段的候选人A。
  2. 在A可用的时间段中,找到具有最少可能出席候选人的时间段a。
  3. 将A放在时间段a上。从表格中移除A和a。
  4. 对每个候选人重复上述过程。

以Python代码的格式,可能如下所示。

d = [["Aoi", 1, 0, ..., 0],
     ["Banri", 1, 1, ..., 1],
     # ...
     ["Nami", 0, 1, ..., 0]]

d_reserved = []

d_return = reserve_each(d, d_reserved)

def reserve_each(d, _reserved):
    d_summed = cal_sums(d) # 在最外层的行/列上添加求和。
    d = d[np.argsort(d_summed[-1, :])]

    for i in range(n):
        di = d[i, 1:]
        if np.max(di) < 0.1:
            if i > 1:
                researve_each(d[i-1:, :], d[:i-1, :])
            else:
                # 警告!!! 或许会变得随机?
                
        di = di[np.argmax(d[-1, 1:] * d[i, 1:])]

        first = 1
        for dij in di:
            if dij == 1:
                dij = dij * first
                first = 0        

        d[i, 1:] = di

    return np.concatenate(d_reserved, d, axis=1))    

def cal_sums(d):
    d = np.concatenate(d, np.sum(d[:, 1:], axis=1))
    d_summed = np.concatenate(d_sorted, [0, np.sum(d[1, 1:], axis=0)])
    return d_summed

然而,我可以想象这种算法可能会失败或者不能提供最佳答案的许多方式。如果有人面临类似的问题并知道更好的方法,我将不胜感激。

英文:

I want to think about the best algorithm which let the interviewer meet maximum number of candidates.
Suppose that there are n candidates and one interviewer. Each of interview will be held for a fixed time, so we can consider that each interview to be given a time slot. Number of time slots are given as m. All candidates are asked to submit whether they are available for each time slots.
If I put it in table format, it looks like this.

1: available
0: not available

         Aoi   Banri  ...   Nami
slot 1    1      1    ...    0
slot 2    0      1    ...    1
 .        .      .    .      .
 .        .      .     .     .
 .        .      .      .    .
slot m    0      1    ...    0
  • Possible approaches 1: solve as a matrix problem

If I interpret this as a matrix problem, it would be reduced to find the Matrix X, expressed as a product of matrices with only one-to-one column exchange, that maximizes trace(AXI).
A is the schedule table, and I is the identity matrix.

Is there any good way to do that?

  • Possible approaches 2: solve as an algorithm problem

If one can think about the best algorithm which always produces best result, it does not necessarily be a matrix problem
One that comes to my mind will be something like that:

  1. Find the candidate A which has minimum number of available time slots.
  2. Among the time slots when A is available, find the slot a which has minimum number of candidates who are possible to attend.
  3. Place A on slot a. Remove both from the table.
  4. Repeat above procedure for each candidates.

In the Python code format, it may look like this.

d=[[Aoi, 1, 0, ..., 0
Banri, 1, 1, ..., 1
.
.
.
Nami,  0, 1, ..., 0
]]

d_reserved=[]

d_return=reserve_each(d, d_reserved)


def reserve_each(d, _reserved):
  d_summed = cal_sums(d) # add summ on rows and columns as the outermost row/column.
  d=d[np.argsort(d_summed[-1, :])]

  for i in range(n):
    di=d[i,1:]
    if np.max(di) &lt; 0.1:
      if i &gt; 1:
        researve_each(d[i-1:, :], d[:i-1,:])
      else:
        # alert!!! perhaps goes random?

    di=di[np.argmax(d[-1,1:]*d[i,1:])]

    first = 1
    for dij in di:
      if dij == 1:
        dij = dij*first
        first = 0        

    d[i,1:]=di

  return np.concatenate(d_reserved, d, axis=1))    


def cal_sums(d):
  d=np.concatenate(d, np.sum(d[:, 1:], axis=1))
  d_summed=np.concatenate(d_sorted, [0, np.sum(d[1, 1:], axis=0)])
  return d_summed

However, I can think many ways this algorithm would fail or may not be provide the best answers.
I would be happy if anyone facing similar problem knows better ways to do that.

答案1

得分: 1

你可以使用最大二分图匹配,但这与区间着色相当相似,因此使用区间着色可能更有效。

按照它们的起始时间对区间进行排序,任意解决绑定关系
让 I_1, I_2,..., In 表示按此顺序排列的区间
对于 j = 1, 2, 3, ... , n
  对于按排序顺序在 I_j 之前并与之重叠的每个区间 I_i
    从 I_j 的考虑中排除 I_i 的标签
  结束
  如果来自 {1, 2,..., d} 的任何标签都没有被排除,则
    为 I_j 分配一个未被排除的标签
  否则
    将 I_j 保留为未标记的
  结束如果
结束对于

这是《算法设计》(K&T,第124页)中的伪代码算法。

英文:

You can use maximum bipartite matching but this is quite similar to interval colouring so using that might be more efficient.

Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2,..., In denote the intervals in this order
For j = 1, 2, 3, ... , n
  For each interval I_i that precedes I_j in sorted order and overlaps it
    Exclude the label of I_i from consideration for I_j
  Endfor
  If there is any label from {1, 2,..., d} that has not been excluded then
    Assign a nonexcluded label to I_j
  Else
    Leave I_j unlabeled
  Endif
Endfor

This is the pseudocode for the algorithm from Algorithm Design by K&T p.g. 124

huangapple
  • 本文由 发表于 2023年6月15日 11:21:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/76478872.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定