Сведение задачи о назначениях к задаче о потоке минимальной стоимости

Задача:

Дана квадратная матрица [math]A_{N\times N}[/math]. Нужно выбрать в ней [math]N[/math] элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.

Очевидно, что решение данной задачи эквивалентно решению следующей:

Задача:

Имеется [math]N[/math] заказов и [math]N[/math] станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

Алгоритм

Пример построенного графа для матрицы [math]A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}[/math]

Сведем задачу о назначениях к задаче нахождения потока минимальной стоимости. Построим ориентированный граф, состоящий из двух частей [math]G[/math] следующим образом:

• Имеется исток [math]S[/math] и сток [math]T[/math].
• В первой части находятся [math]N[/math] вершин, соответствующие строкам матрицы или заказам.
• Во второй [math]N[/math] вершин, соответствующие столбцам матрицы или станкам.
• Между каждой вершиной [math]i[/math] первой части и каждой вершиной [math]j[/math] второй части проведём ребро с пропускной способностью 1 и стоимостью [math]A_{ij}[/math].
• От истока [math]S[/math] проведём рёбра ко всем вершинам [math]i[/math] первой части с пропускной способностью 1 и стоимостью 0.
• От каждой вершины второй части [math]j[/math] к стоку [math]T[/math] проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе [math]G[/math] максимальный поток минимальной стоимости.

Доказательство

Понятно, что величина потока будет равна [math]N[/math]. Заметим, что для каждой вершины [math]i[/math] из первой части найдётся только одна вершина [math]j[/math] из второй части, такая, что поток [math]f(i, j) = 1[/math]. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.

Асимптотика

Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.

Источники

• Задача о назначениях. Решение с помощью min-cost-flow
• Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)