Сведение задачи о назначениях к задаче о потоке минимальной стоимости — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 18 промежуточных версий 9 участников) | |||
Строка 1: | Строка 1: | ||
− | = | + | {{Задача |
− | + | |definition = Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей. | |
− | + | }} | |
+ | Очевидно, что решение данной задачи эквивалентно решению следующей: | ||
+ | {{Задача | ||
+ | |definition = Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость. | ||
+ | }} | ||
− | == | + | == Алгоритм == |
− | Построим | + | [[Файл:pic1.PNG|thumb|right|270px|Пример построенного графа для матрицы <tex>A = \begin{pmatrix} |
− | * Имеется | + | 1 & 2 \\ |
− | * В первой | + | 3 & 4 \end{pmatrix}</tex>]] |
+ | Сведем задачу о назначениях к задаче нахождения потока минимальной стоимости. | ||
+ | Построим ориентированный граф, состоящий из двух частей <tex>G</tex> следующим образом: | ||
+ | * Имеется исток <tex>S</tex> и сток <tex>T</tex>. | ||
+ | * В первой части находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам. | ||
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам. | * Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам. | ||
− | * Между каждой вершиной <tex>i</tex> первой | + | * Между каждой вершиной <tex>i</tex> первой части и каждой вершиной <tex>j</tex> второй части проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>. |
− | * От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой | + | * От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой части с пропускной способностью 1 и стоимостью 0. |
− | * От каждой вершины второй | + | * От каждой вершины второй части <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0. |
Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br /> | Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br /> | ||
− | Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой | + | |
+ | == Доказательство == | ||
+ | Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой части найдётся только одна вершина <tex>j</tex> из второй части, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи. | ||
+ | |||
+ | == Асимптотика == | ||
+ | Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока. | ||
== Источники == | == Источники == | ||
− | [http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow] | + | * [http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow] |
+ | * Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993) | ||
+ | |||
+ | [[Категория:Алгоритмы и структуры данных]] | ||
+ | [[Категория: Задача о потоке минимальной стоимости]] |
Текущая версия на 19:39, 4 сентября 2022
Задача: |
Дана квадратная матрица | . Нужно выбрать в ней элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
Очевидно, что решение данной задачи эквивалентно решению следующей:
Задача: |
Имеется | заказов и станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
Содержание
Алгоритм
Сведем задачу о назначениях к задаче нахождения потока минимальной стоимости. Построим ориентированный граф, состоящий из двух частей
следующим образом:- Имеется исток и сток .
- В первой части находятся вершин, соответствующие строкам матрицы или заказам.
- Во второй вершин, соответствующие столбцам матрицы или станкам.
- Между каждой вершиной первой части и каждой вершиной второй части проведём ребро с пропускной способностью 1 и стоимостью .
- От истока проведём рёбра ко всем вершинам первой части с пропускной способностью 1 и стоимостью 0.
- От каждой вершины второй части к стоку проведём ребро с пропускной способностью 1 и стоимостью 0.
Найдём в полученном графе поток минимальной стоимости.
Доказательство
Понятно, что величина потока будет равна
. Заметим, что для каждой вершины из первой части найдётся только одна вершина из второй части, такая, что поток . Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.Асимптотика
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.
Источники
- Задача о назначениях. Решение с помощью min-cost-flow
- Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)