Изменения

{{Задача|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>N</tex> вершин, соответствующие строкам матрицы или заказам.

* Между каждой вершиной <tex>i</tex> первой доли части и каждой вершиной <tex>j</tex> второй доли части проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли части с пропускной способностью 1 и стоимостью 0.* От каждой вершины второй доли части <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.

 == Доказательство ==Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли части найдётся только одна вершина <tex>j</tex> из второй доличасти, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли части и вершинами второй доли части является решением задачи.

Очевидно, асимптотика Асимптотика этого решения составляет <tex>O(N^5)</tex>равна асимптотике алгоритма, выбранного для поиска потока. 

* [http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993) [[Категория:Алгоритмы и структуры данных]][[Категория: Задача о потоке минимальной стоимости]]