Введение
Проблема комбинаторной оптимизации
Задача назначения является фундаментальной проблемой комбинаторной оптимизации. В своей наиболее общей форме задача формулируется следующим образом: экземпляр задачи содержит некоторое количество агентов и некоторое количество задач. Любой агент может быть назначен для выполнения любой задачи, что влечет за собой определенные затраты, которые могут меняться в зависимости от назначения агента на задачу. Необходимо выполнить как можно больше задач, назначая каждому агенту не более одной задачи и каждой задаче не более одного агента, таким образом, чтобы минимизировать общую стоимость назначения. Альтернативно, описывая задачу с использованием теории графов: задача назначения состоит в поиске в взвешенном двудольном графе соответствия заданного размера, в котором сумма весов ребер минимальна. Если число агентов и число задач равны, то задача называется сбалансированной задачей назначения. В противном случае она называется несбалансированной задачей назначения. Если общая стоимость назначения для всех задач равна сумме затрат по каждому агенту (или сумме затрат по каждой задаче, что в данном случае эквивалентно), то задача называется линейной задачей назначения. Как правило, когда говорят о задаче назначения без дополнительных уточнений, подразумевается линейная сбалансированная задача назначения.
The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized. Alternatively, describing the problem using graph theory:
The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment. If the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called linear assignment. Commonly, when speaking of the assignment problem without any additional qualification, then the linear balanced assignment problem is meant.
Примеры
Предположим, что у компании такси есть три такси (агента) и три клиента (задачи), желающих быть забранными как можно скорее. Компания гордится быстрой подачей машин, поэтому "стоимость" обслуживания конкретного клиента для каждого такси будет зависеть от времени, необходимого такси для прибытия в точку подачи. Это сбалансированная задача назначения. Решение – это такая комбинация такси и клиентов, которая обеспечивает наименьшую общую стоимость. Теперь предположим, что доступно четыре такси, но только три клиента. Это несбалансированная задача назначения. Один из способов ее решения – ввести четвертую фиктивную задачу, например, "бездействие", со стоимостью 0 для назначенного ей такси. Это сводит задачу к сбалансированной задаче назначения, которую затем можно решить обычным способом, получив при этом оптимальное решение исходной задачи. Аналогичные корректировки можно применять для случаев, когда задач больше, чем агентов, когда для выполнения задачи требуется назначить нескольких агентов (например, группа клиентов, превышающая вместимость одного такси), или когда необходимо максимизировать прибыль, а не минимизировать затраты.
Алгоритмы
Наивное решение задачи о назначениях — проверить все возможные назначения и вычислить стоимость каждого из них. Это может быть очень неэффективно, поскольку при n агентах и n задачах существует n! (факториал n) различных назначений. Другое наивное решение — жадно назначать сначала пару с наименьшей стоимостью и удалять соответствующие вершины; затем, среди оставшихся вершин, назначать пару с наименьшей стоимостью; и так далее. Этот алгоритм может привести к неоптимальному решению. Например, предположим, что есть две задачи и два агента со следующими стоимостями: Алиса: Задача 1 = 1, Задача 2 = 2. Джордж: Задача 1 = 5, Задача 2 = 8. Жадный алгоритм назначит Задачу 1 Алисе и Задачу 2 Джорджу, что даст общую стоимость 9; но обратное назначение имеет общую стоимость 7. К счастью, существует множество алгоритмов для нахождения оптимального назначения за время, полиномиальное относительно n. Задача о назначениях является частным случаем транспортной задачи, которая, в свою очередь, является частным случаем задачи о потоке минимальной стоимости, которая является частным случаем линейного программирования. Хотя любую из этих задач можно решить с помощью симплекс-метода, каждая специализация имеет меньшее пространство решений и, следовательно, более эффективные алгоритмы, разработанные для использования его специальной структуры.
Alice: Task 1 = 1, Task 2 = 2. George: Task 1 = 5, Task 2 = 8. The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7. Fortunately, there are many algorithms for finding the optimal assignment in time polynomial in n. The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.
Сбалансированное назначение
В задаче сбалансированного назначения обе части двудольного графа имеют одинаковое количество вершин, обозначаемое n.
Одним из первых алгоритмов сбалансированного назначения, работающих за полиномиальное время, был венгерский алгоритм. Это глобальный алгоритм, основанный на улучшении соответствия вдоль увеличивающих путей (чередующихся путей между несвязанными вершинами). Его временная сложность при использовании кучи Фибоначчи равна , где m – количество ребер. В настоящее время это самое быстрое время работы сильно полиномиального алгоритма для этой задачи. Если все веса – целые числа, то время работы можно улучшить до , но полученный алгоритм является лишь слабо полиномиальным. Если веса – целые числа, и все веса не превышают C (где C > 1 – некоторое целое число), то задача может быть решена за слабо полиномиальное время с помощью метода, называемого масштабированием весов. Помимо глобальных методов, существуют локальные методы, основанные на поиске локальных обновлений (а не полных увеличивающих путей). Эти методы имеют более слабые асимптотические гарантии по времени работы, но часто работают лучше на практике. Эти алгоритмы называются аукционными алгоритмами, алгоритмами проталкивания-возврата или алгоритмами предварительного проталкивания. Некоторые из этих алгоритмов оказались эквивалентными. Некоторые из локальных методов предполагают, что граф допускает совершенное соответствие; если это не так, то некоторые из этих методов могут работать бесконечно долго. Задача поиска совершенного соответствия минимального веса сводится к поиску миноров в матрице смежности графа. Используя лемму об изоляции, совершенное соответствие минимального веса в графе можно найти с вероятностью не менее 1/2. Для графа с n вершинами требуется время.
Неравномерное назначение
В задаче неравновесного назначения большая часть двудольного графа имеет n вершин, а меньшая часть – r < n вершин. Также существует константа s, не превышающая кардинальность максимального паросочетания в графе. Цель состоит в том, чтобы найти паросочетание минимальной стоимости размера ровно s. Наиболее распространенным случаем является случай, когда граф допускает одностороннее совершенное паросочетание (то есть паросочетание размера r), и s = r. Неравновесное назначение можно привести к сбалансированному. Наивное приведение заключается в добавлении новых вершин к меньшей части и соединении их с большей частью ребрами стоимости 0. Однако это требует новых ребер. Более эффективное приведение называется методом удвоения. Здесь новый граф G' строится из двух копий исходного графа G: прямой копии Gf и обратной копии Gb. Обратная копия "инвертируется", так что на каждой стороне G' теперь находится n + r вершин. Между копиями необходимо добавить два типа связывающих ребер (см. Таблицу II). Их работа предлагает алгоритм аппроксимации для задачи назначения (и более общей задачи поиска паросочетания максимального веса), который работает за линейное время при любой фиксированной погрешности.
Обобщение
Когда задача формулируется как задача теории графов, задача назначения может быть расширена от двудольных графов до произвольных графов. Соответствующая задача, заключающаяся в поиске паросочетания в взвешенном графе с максимальной суммой весов, называется задачей о максимальном по весу паросочетании. Другое обобщение задачи назначения – расширение числа множеств, подлежащих сопоставлению, с двух до нескольких. Таким образом, вместо сопоставления агентов задачам, проблема расширяется до сопоставления агентов задачам, временным интервалам и местоположениям. Это приводит к многомерной задаче назначения (MAP).