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

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

Асимптотика

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

Источники