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

Question

Постановка задачи

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

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

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

Откат:

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

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

Возможно, существует D.P. решение, но я еще не вижу его.

Другие мысли

Проблема может быть представлена ​​в матрице NxN, где строки являются «слоты», столбцы «люди», а значения «1» бесплатно и «0» для занятый. Затем мы ищем матрицу идентичности с разбивкой по столбцу в этой матрице. Шаги 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 algorithm.

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

Answer 2

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

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

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

Answer 3

Это Maximum Bipartite Matching problem.

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

Answer 4

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

Подход на основе набора показан ниже на языке 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