Эта проблема может быть смоделирована как
Проблема максимального расхода .
В задаче с максимальным потоком у вас есть ориентированный граф с двумя особыми узлами - источником и приемником. Ребра в графе имеют емкости, и ваша цель состоит в том, чтобы назначить поток через граф из источника в сток, не превышая ни одного из мощностей ребер.
С (очень) тщательно составленным графиком мы можем найти задание, соответствующее вашим требованиям, из максимального потока.
Позвольте мне перечислить требования.
Требуется:
1. Workers are assigned no more than their maximum assignments.
2. Tasks can only be assigned to workers that match one of the task's interests.
3. Every task must be assigned to 3 workers.
4. Every worker must be assigned to at least 1 task.
Дополнительно:
5. Each worker should be assigned a number of tasks proportional to that worker's maximum assignments
6. Each worker should be assigned a variety of tasks.
Я предполагаю, что максимальный поток найден с помощью
Алгоритм Эдмондса-Карпа .
Давайте сначала найдем график, который соответствует требованиям 1-3.
Изобразите график в виде 4 столбцов узлов, где ребра проходят только от узлов в столбце до узлов в соседнем столбце справа.
В первом столбце у нас есть узел источника. В следующем столбце у нас будут узлы для каждого из работников. Исходя из этого, каждый работник имеет преимущество, равное максимальным назначениям этого работника. Это обеспечит выполнение требования 1.
В третьем столбце есть узел для каждой задачи. От каждого работника во втором столбце есть преимущество для каждой задачи, в которой этот работник заинтересован с емкостью 1 (работник интересуется задачей, если пересечение их интересов непусто). Это приведет к выполнению требования 2. При пропускной способности 1 каждый работник будет использовать только 1 из 3 слотов для каждой задачи.
В четвертой колонке у нас есть раковина. От каждой задачи есть грань до уровня приемника 3. Это обеспечит выполнение требования 3.
Теперь мы находим максимальный поток на этом графике, используя алгоритм Эдмондса-Карпа. Если этот максимальный поток меньше, чем 3 * (# of tasks), тогда нет требований по выполнению задания 1-3. Если нет, то есть такое назначение, и мы можем найти его, изучив окончательный расширенный график. На расширенном графике, если есть преимущество от задачи до работника с емкостью 1, то этот работник назначается этой задаче.
Теперь мы изменим наш график и алгоритм для соответствия остальным требованиям.
Сначала давайте выполним требование 4. Это потребует небольшого изменения алгоритма. Изначально установите все мощности от источника до рабочих на 1. Найдите максимальный поток на этом графике. Если поток не равен количеству рабочих, то требования соответствия назначению 4 не существует. Теперь в вашем окончательном остаточном графике для каждого рабочего ребро от источника к этому работнику имеет емкость 0, а обратное ребро имеет емкость 1 Измените их на that worker's maximum assignments - 1 и 0, соответственно. Теперь продолжайте алгоритм Эдмондса-Карпа, как и раньше. По сути, мы сначала нашли такое назначение, чтобы каждому работнику было назначено ровно одно задание. Затем удалите обратный край из этой задачи, чтобы рабочий всегда был назначен хотя бы для одной задачи (хотя это может быть не та задача, которая была назначена в первом проходе).
Теперь давайте выполним требование 5. Строго говоря, это требование просто означает, что мы делим максимальные назначения каждого работника на sum of all worker's maximum assignments / number of tasks. Это вполне может не иметь удовлетворительного назначения. Но это нормально. Инициализируйте наш график с этими новыми максимальными назначениями. Запустите Эдмондс-Карп. Если он находит поток, который насыщает края от задач к погружению, мы закончили. В противном случае мы можем увеличить пропускную способность от приемника до рабочих на остаточном графике и продолжить работу Edmonds-Karp. Повторяйте, пока мы не насыщаем края в раковину. Не увеличивайте мощности настолько сильно, чтобы работнику было назначено слишком много задач. Кроме того, технически приращение для каждого работника должно быть пропорционально максимальным назначениям этого работника. И то, и другое легко сделать.
Наконец, давайте выполним требование 6. Это немного сложно. Сначала добавьте столбец между рабочими и задачами и удалите все ребра из рабочих задач. В этом новом столбце для каждого работника добавьте узел для каждого из этих рабочих интересов. Из каждого из этих новых узлов добавьте ребро к каждой задаче с совпадающим интересом с емкостью 1. Добавьте ребро от каждого работника к каждому из его узлов интереса с емкостью 1. Теперь поток в этом графе обеспечит это, если работник назначается n задач, то пересечение объединения интересов этих задач с интересами этого работника имеет размер не менее n. Снова, возможно, что есть удовлетворяющее назначение без этого назначения, но нет ни одного с ним. Мы можем справиться с этим так же, как и с требованием 5: запустить Edmonds-Karp до завершения, если не выполняется удовлетворительное назначение, увеличить пропускную способность от рабочих к их интересующим узлам и повторить.
Обратите внимание, что в этом измененном графике мы больше не удовлетворяем требованию 3, поскольку один работник может быть назначен нескольким / всем слотам задачи, если пересечение их интересов имеет размер больше 1. Мы можем это исправить. Добавьте новый столбец узлов между узлами интереса и узлами задачи и удалите ребра между этими узлами. Для каждого сотрудника в новом столбце вставьте узел для каждой задачи (чтобы у каждого сотрудника был свой узел для каждой задачи). От этих новых узлов к соответствующей задаче справа добавьте ребро с емкостью 1. От узла интересов каждого работника к узлам задач этого работника добавьте ребро с емкостью 1 от каждого интереса к каждой соответствующей задаче.
-
РЕДАКТИРОВАТЬ: Позвольте мне попытаться объяснить это немного. Пусть -(n)-> будет ребром с n-емкостью.
Ранее у нас было worker-(1)->task для каждой пары работник-задача с совпадающим интересом. Теперь у нас есть worker-(k)->local interest-(1)->local task-(1)->global task. Теперь вы можете думать о задаче, которая соответствует паре рабочий-интерес. Первое преимущество говорит о том, что для работника каждый из его интересов может быть сопоставлен с k задачами. Второе преимущество говорит о том, что интересы каждого работника могут быть сопоставлены только один раз с каждой работой. Третье ребро говорит о том, что каждое задание может быть назначено только один раз каждому работнику. Обратите внимание, что вы можете передать несколько потоков от рабочего к локальной задаче (равных размеру пересечения их интересов), но только 1 поток от рабочего к глобальному узлу задачи из-за третьего ребра.
-
Также обратите внимание, что мы не можем правильно смешать это приращение с одним для требования 5 правильно. Однако мы можем запустить весь алгоритм по одному разу для каждой емкости {1,2, ..., r} для рабочих -> интересов. Затем нам нужен способ ранжировать назначения. То есть, если мы ослабим требование 5, мы сможем лучше выполнить требование 6 и наоборот. Однако есть другой подход, который я предпочитаю для смягчения этих ограничений.
Лучший подход к ослаблению требований (по мотивам / по шаблону templatetypedef)
Когда мы хотим иметь возможность ослабить множество требований (например, 5 и 6), мы можем смоделировать это как проблему максимального расхода с минимальными затратами. Это может быть проще, чем инкрементальный поиск, который я описал выше.
Например, для требования 5 установите все ребра затрат на 0. У нас есть начальное ребро от источника к работнику с мощностью, равной worker's maximum assignments / (sum of all worker's maximum assignments / number of tasks) и со стоимостью 0. Затем вы можете добавить еще одно ребро с помощью оставшаяся емкость для этого работника и стоимость 1. Другая возможность может заключаться в использовании некоторой прогрессивной стоимости, так что при добавлении задач к работнику увеличивается стоимость добавления другой задачи для этого пользователя. Например. вместо этого вы могли бы разделить оставшиеся рабочие места работника на отдельные ребра с затратами 1,2,3,4,....
Подобное можно было бы затем сделать между рабочими узлами и узлами локального интереса для требования 6. Взвешивание должно быть сбалансировано, чтобы отразить относительную важность различных требований.
Этот метод также достаточен для обеспечения выполнения требования 4. Кроме того, затраты для требования 5, вероятно, должны быть сделаны такими, чтобы они были пропорциональны максимальным назначениям работника. Тогда назначение 1 дополнительного задания работнику с максимум 100 не будет стоить столько же, сколько назначение дополнительного работника с максимумом 2.
Анализ сложности
Пусть n = # of employees, m = # of tasks, k = max interests for a single task/worker, l = # of interests, j = maximum of maximum assignments.
Требование 3 подразумевает, что n = O (m). Давайте также предположим, что l = O(m) и j = O(m).
В меньшем графе (до изменения по требованию 6) граф имеет n + m + 2 = O(m) вершин и самое большее n + m + k*min(n, m) = O(km) ребер.
После изменения у него есть 2 + n + n * l + n * m + m = O(nm) вершин и n + k * n + k * m * n + n * m + m = O(kmn) ребер (технически нам может потребоваться j * n + j * l больше узлов и ребер, чтобы не было нескольких ребер от одного узла к другому, но это не изменит асимптотику связанно). Также обратите внимание, что нет необходимости в ребре> j.
Используя минимальную формулировку максимального потока, мы можем найти решение в O(VEBlogV), где V = # vertices, E = # edges и B = max capacity on a single edge. В нашем случае это дает O(kjn^2m^2log(nm)).