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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 16 промежуточных версий 7 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
{{Задача
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
+
|definition = Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
+
}}
 +
Очевидно, что решение данной задачи эквивалентно решению следующей:
 +
{{Задача
 +
|definition = Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
 +
}}
  
== Сведение к задаче о потоке минимальной стоимости ==
+
== Алгоритм ==
Построим двудольный граф <tex>G</tex> следующим образом:
+
[[Файл:pic1.PNG|thumb|right|270px|Пример построенного графа для матрицы <tex>A = \begin{pmatrix}
* Имеется сток <tex>S</tex> и исток <tex>T</tex>.
+
1 & 2 \\
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.  
+
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>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
+
* Между каждой вершиной <tex>i</tex> первой части и каждой вершиной <tex>j</tex> второй части проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.
+
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой части с пропускной способностью 1 и стоимостью 0.
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</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>j</tex> из второй доли, такая, что поток <tex>F_{ij} = 1</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)
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория: Задача о потоке минимальной стоимости]]

Текущая версия на 15:24, 7 января 2017

Задача:
Дана квадратная матрица [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]. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.

Асимптотика[править]

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

Источники[править]