http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=83.149.2.5&*Викиконспекты - Вклад участника [ru]2026-08-05T10:50:32ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2%D0%B4%D0%BE%D0%BB%D1%8C_%D0%BF%D1%83%D1%82%D0%B5%D0%B9_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=18554Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости2012-02-29T18:10:11Z<p>83.149.2.5: /* Идея */</p>
<hr />
<div>==Идея==<br />
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> и дополнять поток вдоль этого пути. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.<br />
<br />
==Реализация==<br />
<br />
'''for''' <tex>e \in E</tex> {<br />
<tex>f[e] \leftarrow 0</tex><br />
}<br />
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {<br />
<tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex><br />
дополнить поток <tex>f</tex> вдоль <tex>P</tex><br />
}<br />
<br />
==Корректность==<br />
Непосредственно следует из [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теоремы Форда-Фалкерсона о потоке минимальной стоимости]].<br />
<br />
==Асимптотика==<br />
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>. <br />
<br />
Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>.<br />
<br />
== Литература ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>83.149.2.5http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B5_%D0%BE_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B5_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=18553Сведение задачи о назначениях к задаче о потоке минимальной стоимости2012-02-29T18:06:59Z<p>83.149.2.5: /* Сведение к задаче о потоке минимальной стоимости */</p>
<hr />
<div>== Постановка задачи ==<br />
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.<br />
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.<br />
<br />
== Сведение к задаче о потоке минимальной стоимости ==<br />
[[Файл:pic1.PNG|thumb|right|275x250px|Пример построенного графа для матрицы А]]<br />
Построим ориентированный граф, состоящий из двух частей <tex>G</tex> следующим образом:<br />
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.<br />
* В первой части находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам. <br />
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.<br />
* Между каждой вершиной <tex>i</tex> первой части и каждой вершиной <tex>j</tex> второй части проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.<br />
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой части с пропускной способностью 1 и стоимостью 0.<br />
* От каждой вершины второй части <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.<br />
<br />
Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br /><br />
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой части найдётся только одна вершина <tex>j</tex> из второй части, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.<br />
<br />
== Асимптотика == <br />
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.<br />
<br />
== Источники ==<br />
* [http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>83.149.2.5