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

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

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

Асимптотика

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

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости&oldid=59057»