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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Постановка задачи == * Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> э…»)
 
Строка 14: Строка 14:
 
Найдём в полученном графе <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_{ij} = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.
 +
 +
== Источники ==
 +
[http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]

Версия 11:41, 14 января 2011

Постановка задачи

  • Дана квадратная матрица [math]A_{N\times N}[/math]. Нужно выбрать в ней [math]N[/math] элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
  • Имеется [math]N[/math] заказов и [math]N[/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_{ij} = 1[/math]. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

Источники

Задача о назначениях. Решение с помощью min-cost-flow