Сведение задачи о назначениях к задаче о потоке минимальной стоимости — различия между версиями
(→Сведение к задаче о потоке минимальной стоимости) |
VVolochay (обсуждение | вклад) |
||
Строка 4: | Строка 4: | ||
== Сведение к задаче о потоке минимальной стоимости == | == Сведение к задаче о потоке минимальной стоимости == | ||
− | [[Файл:pic1.PNG|thumb|right| | + | [[Файл:pic1.PNG|thumb|right|270px|Пример построенного графа для матрицы <tex>A = \begin{pmatrix} |
1 & 2 \\ | 1 & 2 \\ | ||
3 & 4 \end{pmatrix}</tex>]] | 3 & 4 \end{pmatrix}</tex>]] |
Версия 23:30, 5 июня 2012
Содержание
Постановка задачи
- Дана квадратная матрица . Нужно выбрать в ней элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
- Имеется заказов и станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
Сведение к задаче о потоке минимальной стоимости
Построим ориентированный граф, состоящий из двух частей
следующим образом:- Имеется исток и сток .
- В первой части находятся вершин, соответствующие строкам матрицы или заказам.
- Во второй вершин, соответствующие столбцам матрицы или станкам.
- Между каждой вершиной первой части и каждой вершиной второй части проведём ребро с пропускной способностью 1 и стоимостью .
- От истока проведём рёбра ко всем вершинам первой части с пропускной способностью 1 и стоимостью 0.
- От каждой вершины второй части к стоку проведём ребро с пропускной способностью 1 и стоимостью 0.
Найдём в полученном графе поток минимальной стоимости.
Понятно, что величина потока будет равна . Заметим, что для каждой вершины из первой части найдётся только одна вершина из второй части, такая, что поток . Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.
Асимптотика
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.
Источники
- Задача о назначениях. Решение с помощью min-cost-flow
- Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)