Участник:Anastasy/Алгоритм Диница: различия между версиями
Anastasy (обсуждение | вклад) (Новая страница: «== Постановка задачи == === Общее описание алгоритма === Алгоритм Диница -- полиномиальный ал…») |
Anastasy (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | Алгоритм Диница | + | Алгоритм Диница — полиномиальный алгоритм, предназначенный для поиска [[Поиск максимального потока в транспортной сети| максимального потока в транспортной сети]]. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма <math>O(nm^2)</math>. Достижение этой оценки стало возможно благодаря введению понятий блокирующего потока и слоистой сети. |
| + | |||
| + | Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. | ||
| + | Алгоритм Диница схож с алгоритмом Эдмондса-Карпа, но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей (ведь именно такими путями и являются пути в блокирующем потоке слоистой сети). | ||
| + | |||
| + | Идея алгоритма состоит в следующем. Сначала величине потока присваивается 0: <math>f(u, v)=0</math> для любых <math>u, v \in V</math>. | ||
Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. | Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. | ||
| + | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Математическая постановка задачи приведена в статье ..., мы будем использовать введённые в ней обозначения. | Математическая постановка задачи приведена в статье ..., мы будем использовать введённые в ней обозначения. | ||
Версия 13:17, 18 октября 2017
1 Постановка задачи
1.1 Общее описание алгоритма
Алгоритм Диница — полиномиальный алгоритм, предназначенный для поиска максимального потока в транспортной сети. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма [math]O(nm^2)[/math]. Достижение этой оценки стало возможно благодаря введению понятий блокирующего потока и слоистой сети.
Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. Алгоритм Диница схож с алгоритмом Эдмондса-Карпа, но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей (ведь именно такими путями и являются пути в блокирующем потоке слоистой сети).
Идея алгоритма состоит в следующем. Сначала величине потока присваивается 0: [math]f(u, v)=0[/math] для любых [math]u, v \in V[/math].
Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается.
1.2 Математическое описание алгоритма
Математическая постановка задачи приведена в статье ..., мы будем использовать введённые в ней обозначения.
Введём необходимые определения.
Остаточной сетью [math]G^R[/math] по отношению к сети [math]G[/math] и некоторому потоку [math]f[/math] в ней называется сеть, в которой каждому ребру [math](u,v) \in G[/math] с пропускной способностью [math]c_{uv}[/math] и потоком [math]f_{uv}[/math] соответствуют два ребра:
- [math](u,v)[/math] с пропускной способностью [math]c_{uv}^R = c_{uv} - f_{uv}[/math]
- [math](v,u)[/math] с пропускной способностью [math]c_{vu}^R = f_{uv}[/math]
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро [math](u,v)[/math], так и [math](v,u)[/math].
