Алгоритм планирования назначения (N человек с N слотами для свободных занятых, удовлетворенность требованиями)

Описание проблемы

У нас есть один работодатель, который хочет опросить людей N, и поэтому делает N слотов для интервью. У каждого человека есть график свободных занятий для этих слотов. Дайте алгоритм, который планирует N людей в N слотов, если это возможно, и вернуть флаг/ошибку/etc, если это невозможно. Какова самая быстрая возможная сложность выполнения?

Мои подходы до сих пор

Наивный: есть N! способы запланировать N людей. Пройдите через все из них, для каждой перестановки проверьте, выполнимо ли это. O (n!)

Откат:

Ищите какие-либо слоты для интервью, в которых может быть только 1 человек. Запланируйте человека, удалите его из списка кандидатов и удалите слот.
Ищите кандидатов, которые могут попасть только в 1 слот. Запланируйте человека, удалите его из списка кандидатов и удалите слот.
Повторяйте 1 и 2, пока не будет таких комбинаций.
Выберите человека, скопируйте его случайным образом в один из доступных слотов. Помните эту операцию.
Повторяйте 1, 2, 3 до тех пор, пока у нас не будет графика или не будет неразрешимого конфликта. Если у нас есть график, верните его. Если есть неразрешимый конфликт, откат.

Это самый худший случай O (n!), я думаю - это не лучше.

Там может быть D.P. решение, но я еще не вижу его.

Другие мысли

Проблема может быть представлена в матрице NxN, где строки являются "слотами", столбцы - "люди", а значения "1" свободны и "0" для занятости. Затем мы ищем матрицу идентичности с разбивкой по столбцу в этой матрице. Шаги 1 и 2 ищут строку или столбец только с одним "1". (Если ранг матрицы равен N, то это означает, что существует решение, но противоположное не выполняется) Другой способ взглянуть на это - обработать матрицу как неважную направленную графовую матрицу графа. Затем каждый из узлов представляет 1 кандидата и 1 слот. Затем мы ищем набор ребер, чтобы каждый node в графе имел один исходящий ребро и один входящий фронт. Или, с 2x узлами, это будет двудольный граф.

Пример матрицы:

Ответ 1

Как вы указали, проблема эквивалентна задаче нахождения максимального совпадения в двудольном графе (один набор вершин - это набор людей, а другой - на множестве слотов, есть край между человеком и слот, если человек доступен для этого слота).

Эта проблема может быть решена с помощью алгоритма Hopcroft-Karp.

Сложность O (n ^ (5/2)) в худшем случае, лучше, если граф разрежен.

Ответ 2

Что касается подхода к программированию с ограничениями, его можно моделировать по-разному, например, с помощью матричного подхода и подхода, основанного на наборе.

Подход, основанный на наборе, показан ниже на языке CP высокого уровня MiniZinc. s - это люди, которые доступны каждый временной интервал (с использованием заданной нотации); переменными решения являются массив 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,5 мс), например. время 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

Модель матричного подхода находится здесь (без секции вывода) и использует стандартный метод программирования Integer: 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

Ответ 3

Это Проблема с максимальным двупартийным соответствием.

В зависимости от плотности графика наиболее быстрым решением является, вероятно, алгоритм Hopcroft-Karp, который длится не более O (N ^ (5/2)), но, вероятно, намного быстрее.

Ответ 4

Я считаю, что вы можете использовать сетевые потоки.

Создайте вершину u_i для кандидата i и вершину v_j для слота j.
Создайте источник node s и поместите (направленный) ребро от s к каждому u_i емкости 1.
Сделайте раковину node t и поместите ребро от каждого v_j до t вместимость 1.
Поместите ребро от u_i до v_j, если кандидат i может взять интервью в слоте j.
У нас есть O(N) вершины и O(N^2) ребра, максимально возможный поток N.
Найдите максимальный поток, используя, например, алгоритм Ford-Fulkerson, который принимает O(E*f), где E - количество ребра и f - это значение максимального потока, поэтому требуется O(N^3).
Если максимальный поток N, тогда у нас есть расписание: если ребро (u_i,v_j) имеет поток 1, то мы проводим собеседование с кандидатом i в слоте j, иначе это невозможно.

По теореме об интегральном потоке максимальный поток будет иметь целые потоки на ребрах, равные 0 или 1, поэтому у нас есть действующий график.