Описание проблемы
У нас есть один работодатель, который хочет опросить людей N, и поэтому делает N слотов для интервью. У каждого человека есть график свободных занятий для этих слотов. Дайте алгоритм, который планирует N людей в N слотов, если это возможно, и вернуть флаг/ошибку/etc, если это невозможно. Какова самая быстрая возможная сложность выполнения?
Мои подходы до сих пор
Наивный: есть N! способы запланировать N людей. Пройдите через все из них, для каждой перестановки проверьте, выполнимо ли это. O (n!)
Откат:
Это самый худший случай O (n!), я думаю - это не лучше.
Там может быть D.P. решение, но я еще не вижу его.
Другие мысли
Проблема может быть представлена в матрице NxN, где строки являются "слотами", столбцы - "люди", а значения "1" свободны и "0" для занятости. Затем мы ищем матрицу идентичности с разбивкой по столбцу в этой матрице. Шаги 1 и 2 ищут строку или столбец только с одним "1". (Если ранг матрицы равен N, то это означает, что существует решение, но противоположное не выполняется) Другой способ взглянуть на это - обработать матрицу как неважную направленную графовую матрицу графа. Затем каждый из узлов представляет 1 кандидата и 1 слот. Затем мы ищем набор ребер, чтобы каждый node в графе имел один исходящий ребро и один входящий фронт. Или, с 2x узлами, это будет двудольный граф.
Пример матрицы:
1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1
Как вы указали, проблема эквивалентна задаче нахождения максимального совпадения в двудольном графе (один набор вершин - это набор людей, а другой - на множестве слотов, есть край между человеком и слот, если человек доступен для этого слота).
Эта проблема может быть решена с помощью алгоритма Hopcroft-Karp.
Сложность O (n ^ (5/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
Это Проблема с максимальным двупартийным соответствием.
В зависимости от плотности графика наиболее быстрым решением является, вероятно, алгоритм Hopcroft-Karp, который длится не более O (N ^ (5/2)), но, вероятно, намного быстрее.
Я считаю, что вы можете использовать сетевые потоки.
u_i для кандидата i и вершину v_j для слота j.s и поместите (направленный) ребро от s к каждому u_i емкости 1.t и поместите ребро от каждого v_j до t вместимость 1.u_i до v_j, если кандидат i может взять интервью в слоте j.O(N) вершины и O(N^2) ребра, максимально возможный поток N.O(E*f), где E - количество ребра и f - это значение максимального потока, поэтому требуется O(N^3).N, тогда у нас есть расписание: если ребро (u_i,v_j) имеет поток 1, то мы проводим собеседование с кандидатом i в слоте j, иначе это невозможно.По теореме об интегральном потоке максимальный поток будет иметь целые потоки на ребрах, равные 0 или 1, поэтому у нас есть действующий график.