预约调度算法(N人有N个自由忙位,约束满足)

Question

问题陈述

我们有一个雇主想要采访N人,因此会有N个面试时段.每个人都有自由忙碌的时间表.给出一个算法,如果可能的话,将N个人调度到N个插槽中,如果不可能,则返回标志/错误/等.什么是最快的运行时复杂性？

到目前为止我的方法

天真:有N!安排N人的方法.浏览所有这些,对于每个排列,检查它是否可行.上! )

回溯:

1. 寻找任何只能有1个人的面试时间段.安排此人,将其从候选人列表中删除并删除该插槽.
2. 寻找任何只能进入1个位置的候选人.安排此人,将其从候选人列表中删除并删除该插槽.
3. 重复1和2,直到没有更多这样的组合.
4. 选择一个人,将他们随机安排到他们的一个可用插槽中.记住这个操作.
5. 重复1,2,3,直到我们有一个时间表或存在无法解决的冲突.如果我们有时间表,请将其退回.如果存在无法解决的冲突,请回溯.

这是O(n!)最糟糕的情况,我认为 - 这不是更好.

可能还有DP解决方案 - 但我还没有看到它.

其他想法

问题可以用NxN矩阵表示,其中行是"槽",列是"人",值是"1"表示空闲,"0"表示忙.然后,我们在这个矩阵中寻找一个行列交换的Identity Matrix.步骤1和2正在寻找只有一个"1"的行或列.(如果矩阵的秩是= N,那意味着有一个解决方案.但相反的情况并不成立)另一种看待它的方法是将矩阵视为未加权的有向图边缘矩阵.然后,每个节点代表1个候选和1个时隙.然后我们寻找一组边,以便图中的每个节点都有一个输出边和一个输入边.或者,对于2x节点,它将是一个二分图.

矩阵示例:

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

Answer 1

正如您所指出的,问题等同于在二分图中找到最大匹配的问题(一组顶点是一组人,另一组在一组槽中,一个人和一个槽之间有一条边如果此人可用于此插槽).

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

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

Answer 2

至于约束编程方法,它可以以不同的方式建模,例如使用矩阵方法和基于集合的方法.

基于集合的方法在高级CP语言MiniZinc中显示如下.s是每个时段可用的人(使用set notation); 决策变量是数组x(每次应该分配给哪个人).

include "globals.mzn"; 
int: n = 4;

% free persons per time slot
array[1..n] of set of int: s =  
[{1,2,3,4},
 {2,3},
 {1,4},
 {1,4}];


% decision variables
% the assignment of persons to a slot (appointment number 1..n)
array[1..n] of var 1..n: x;

solve satisfy;

constraint
  % ensure that the appointed person for the time slot is free
  forall(i in 1..n) (
    x[i] in s[i]
  )
  /\ % ensure that each person get a distinct time slot
  alldifferent(x)
;

output [ show(x) ];

该模型输出这4个解(在0.5ms内),例如时间1分配给人3等.

x: [3, 2, 4, 1]
----------
x: [2, 3, 4, 1]
----------
x: [3, 2, 1, 4]
----------
x: [2, 3, 1, 4]

MiniZinc模型在这里:appointment_scheduling_set.mzn

矩阵方法模型在这里(没有输出部分)并使用标准的整数编程方法:appointment_scheduling.mzn.

int: n = 4;

% rows are time slots
% columns are people
array[1..n, 1..n] of int: m = array2d(1..n, 1..n,
[
1, 1, 1, 1,
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
]);

% decision variables
% the assignment of persons to a slot (appointment number 1..n)
array[1..n, 1..n] of var 0..1: x;

solve satisfy;

constraint
  forall(i in 1..n) (
    % ensure a free slot
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1

    /\ % ensure one assignment per slot and per person
    sum([x[i,j] | j in 1..n]) = 1
    /\
    sum([x[j,i] | j in 1..n]) = 1
  )
;

这个模型的解决方案是相同的,虽然以另一种(并且更详细)的方式呈现,并且 - 当它发生时 - 以与基于集合的方法相同的顺序

slot 1: 3
slot 2: 2
slot 3: 4
slot 4: 1
----------
slot 1: 2
slot 2: 3
slot 3: 4
slot 4: 1
----------
slot 1: 3
slot 2: 2
slot 3: 1
slot 4: 4
----------
slot 1: 2
slot 2: 3
slot 3: 1
slot 4: 4