Cтраница 1
Преимущества потоковых алгоритмов Клейна и Басакера-Гоуэна - простая логика, хорошая интерпретируемость получаемых результатов, удобство задания, размещения и обработки массивов информации, простота коррекции решений при изменении данных. Оба алгоритма имитируют процесс получения решений плановыми органами вручную и широко используются при плановых расчетах. [1]
Карза - н о в, Потоковые алгоритмы. [2]
Рациональный путь изменения значений величин i f и Wj заключается в следующем. Исходя из характера потокового алгоритма, целесообразно ограничиться только такими дугами, у которых узел rt помечен, а узел kj не помечен. [3]
Новая постановка задачи позволяет предложить эффективные потоковые алгоритмы вычисления управлений ( поступлений и продвижений), по-новому осмыслить задачу, сформулировать на языке потоков в сетях условия для существования решения и показать целочисленность этих решений. [4]
Допустим, что у нас есть орграф G с заданными пропускными способностями и нам нужно найти максимальный поток между каждой парой его вершин. Конечно, мы можем просто применить потоковый алгоритм 2 () раз. [5]
Любую из этих задач можно решить с помощью потоковых алгоритмов, применяя их к различным парам вершин. [6]
К счастью, не все еще потеряно. Эдмондс и Карп ( 1970, 1972) и Диниц ( 1970) нашли такие потоковые алгоритмы, работа которых завершается ( за конечное число шагов) при произвольных пропускных способностях. Можно спросить, к чему такие сложности, если на практике пропускные способности должны быть всегда представлены в виде рациональных чисел. Алгоритм Эдмондса и Карпа ближе к исходной идее, и мы сначала обсудим его. Этот алгоритм базируется на следующей теореме. [7]
Иногда бывает желательно представить сложный поток как сумму простых потоков. Это бывает полезно не столько из-за того, что такая декомпозиция нужна на практике, а потому что она дает лучшее понимание природы потоков в сетях и служит удобным средством для обоснования многих потоковых алгоритмов. [8]
Сначала напомним, что задачу о нахождении наименьшего uu - разреза в графе ( или орграфе) можно решить с помощью теоремы о максимальном потоке и минимальном разрезе ( теорема 2.1.4) или, используя различные потоковые алгоритмы, описанные в разд. Применяя эти результаты к каждой паре вершин и, v, можно решить задачу о минимальном разрезе для всего графа. Изящную взаимосвязь между минимальными разрезами для всех пар и, г) описывает принадлежащая Гомори и Ху теорема о потоково-эквивалентном дереве ( теорема 2.3.2), которая еще сыграет свою роль в предстоящих рассмотрениях. [9]
Соотношения ( 4), ( 5) при заданном базисе позволяют построить решение с помощью элементарных алгебраических операций. При этом обращения базисной матрицы не требуется: ее элементы являются индикаторами принадлежности дуг базисного дерева цепям, соединяющим корень ( узел 0) с остальными вершинами графа. Это свойство предопределяет значительные преимущества потоковых алгоритмов перед стандартными методами линейного программирования. [10]
Различные стороны функционирования систем газо - и нефтеснабжения отражаются в математических моделях, основой которых является построение потока в расчетной сети. Частично эти особенности можно учесть, задавая структуру и параметры этой сети специальным образом. В некоторых случаях приходится видоизменять не только сеть, но и условия, накладываемые на поток. Предполагается, что алгоритмы решения этих задач известны читателю. Рассмотрим видоизменения стандартных потоковых алгоритмов, которые применительно к расчету потокораспределения в сетях транспорта нефти и газа позволяют существенно повысить эффективность вычислений. [11]
Отложим на минуту доказательство и сделаем несколько замечаний. К счастью, для этого есть простая процедура. Действительно, если мы создадим алгоритм для нахождения какой-нибудь / - увеличивающей цепи, то сможем, вероятно, найти и кратчайшую цепь. До появления работы Эдмондса и Карпа использовались сходящиеся ( в действительности полиномиальные) потоковые алгоритмы, но их полиноми-альность не была установлена, поскольку не была осознана значимость того факта, что они выбирают кратчайшую увеличивающую цепь. [12]
Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил. Назовем процедуру помечивания состоятельной, если всякий раз, когда имеется некоторое множество помеченных, но не просмотренных вершин, выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу. Таккер ( 1977) доказал, что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда - Фалкерсона, то алгоритм завершает работу и приводит к максимальному потоку. Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза. [13]