Задача о максимальном потоке сети
Изучение определений и теорем потока сети, определение сводимости некоторых задач о максимальном потоке. Описание алгоритмов локального и кратчайшего увеличения цепей сети. Метод поразрядного сокращения невязок и Динамические деревья Слейтора-Тарьяна.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 22.11.2013 |
| Размер файла | 512,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
38
Реферат
Задача о максимальном потоке сети
Содержание
Введение
Основные определения и теоремы
Сводимость некоторых задач о максимальном потоке в сети
Алгоритм Форда-Фалкерсона
Алгоритм кратчайших увеличивающих цепей
Алгоритм локально-максимального увеличения
Алгоритм Диница
Метод поразрядного сокращения невязок
Алгоритм Карзанова
Алгоритм Малхотри-Кумара-Махешвари
Алгоритм Галила-Наамада
Динамические деревья Слейтора-Тарьяна
Алгоритм Голдберга-Таряна
Алгоритм CHM
Алгоритм Кинга
Алгоритм Голдберга-Рао
Список использованной литературы
Введение
Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.
60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательныхбесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести кфундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он используетпредпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Раопредложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.
К сожалению, в России, в настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли встретите что-либо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются.
Основные определения и теоремы
В этой главе приведены определения и теоремы без доказательства из [1] и [2].
Рассмотрим орграф G = (V, E), где V - множество вершин, E - множество ребер. |V| = n, |E| = m. Под сетью понимается пара S = (G, c), где c: ER - функция, ставящая каждой дуге в соответствие положительное вещественное число - пропускную способность.
Вы делим в сети 2 вершины: s (источник) и t (сток).
Назовем функцию f: ER потоком в сети S, если она удовлетворяет следующим условиям:
1.(v, u)E, 0 f(v, u) c(v, u) - ограничение, накладываемое пропускной способностью дуги.
2.vV \ {s, t}, - закон сохранения потока[1] , . Величиной потока f, назовем Div(s).
Под максимальным потоком сети понимается поток из s в t максимальной величины.
Разрезом P(W) сети S, где WV (W, WV), назовем множество дуг (u, v)E, таких, что u V и vV\W.
Поток через разрез определяется так: f(W, V\W) .
Под пропускной способностью разреза понимается.
Минимальным разрезом сети называется произвольный разрез P(W), sW и tV\W с минимальной пропускной способностью.
Дадим следующие теоремы без доказательства:
1. Если sW и tV\W, то величина потока из s в t равна f(W, V\W) - f(V\W, A).
2. Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения. (Теорема Форда-Фалкерсона).
Допустимой дугой e = (u, v) относительно потока f назовем дугу, для которой выполняется одно из двух следующих условий:
а). e = (u, v) и f(e) < c(e).
б). e = (v, u) и f(e) > 0.
Если для допустимой дуги выполнено первое условие, назовем ее согласованной, иначе не согласованной.
Увеличивающей цепью (длины l) из s в t называется произвольная знакопеременная последовательность (попарно различных) вершин и дуг: v0, e1, v1, e2, v2, …, vl-1, el,vl , где v0 = s, vl = t, для всех il. Все дуги должны быть допустимы.
Зная увеличивающую цепь, мы можем увеличить поток в этой цепи на
,
где
Чтобы увеличить поток, необходимо увеличить его значение на в каждой согласованной дуге цепи и уменьшить в каждой несогласованной.
Следующие 3 условия эквивалентны:
1. Поток из s в t максимален.
2. Не существует увеличивающей цепи для f.
3. Величина потока равна c(W, V\W) для некоторого WV, такого что sW, а tW.
Теорема о Декомпозиции.
Любой поток из s в t можно разделить на следующие примитивы:
а). Цепь из s в t с потоком величины .
б). Циклы с потоком величины .
Поток может распасться не более чем на m примитивов.
Сводимость некоторых задач о максимальном потоке в сети
Большинство разнообразных сетей и условий существования потока в них, которые могут возникнуть при рассмотрении различных приложений задачи о максимальном потоке, сводятся к поиску максимального потока в ориентированной сети с одним источником и стоком, и заданными вещественными верхними границами пропускных способностей дуг сети. Рассмотрим наиболее распространенные частные случаи, которые могут быть приведены к оригинальной постановке задачи.
Случай нескольких источников и стоков.
В этом случае все узлы сети делятся на 3 группы: S - множество источников, T - множество стоков и R - множество промежуточных узлов. Поток может следовать из любого источника в любой сток. В этом случае сеть модифицируется следующим образом:
Добавим новую вершину S* и соединим ее дугами со всеми вершинами из множества S. Вершина S* называется суперисточником. Добавим новую вершину T* и соединим ее дугами со всеми вершинами из множества T. Вершина T* называется суперстоком. Пропускные способности всех новых дуг положим равными ?.
Очевидно, что поиск максимального потока из вершин множества S в вершины множества T равносилен поиску максимального потока из S* в T*.
Случай ограниченной пропускной способности вершин.
Если пропускные способности наряду с дугами имеют и узлы сети, то каждую вершину v, имеющую пропускную способность c(v), следует заменить двумя (v' и v''), соединенными дугой (v', v'') и c(v', v'') = c(v).
Случай существования нижних границ пропускных способностей дуг.
Если рассматриваемой задаче поток, проходящий по дуге u, может принимать значения l(u) ? f(u) ? c(u), то функция l(u) рассматривается как уже имеющийся в сети поток и поиск максимального потока следует начинать не с нулевого потока, а с потока l(u).
Случай неориентированных и смешанных сетей.
Поток по неориентированной дуге (v, w) должен удовлетворять следующим условиям:
f(v, w) ? c(v, w)
f(w, v) ? c(v, w)
f(v, w)*f(w, v) = 0
В этом случае замена неориентированной дуги двумя противоположно направленными ориентированными дугами с одинаковой пропускной способностью c(c, w) сведет задачу к эквивалентной задаче на орграфе, что доказано в [3]. Аналогично ориентированные сети сводятся к неориентированным. (Кроме сетей с единичными пропускными способностями)
Пропускные способности различных типов.
Различаются случаи целочисленных, вещественных и единичных пропускных способностей. Предполагается, что приводимые далее алгоритмы рассматриваются на сетях с вещественными пропускными способностями, кроме специально оговоренных случаев.
Алгоритм Форда-Фалкерсона
Впервые был предложен в 1956г. До этого времени задача решалась с помощью методов линейного программирования, что было крайне не эффективно. Алгоритм является псевдополиномиальным и имеет оценку O(nm log U), где m = |E|, n = |V|, U = max(Cij).
Алгоритм начинает свою работу с нулевого потока и на каждой своей итерации увеличивает поток в сети. На каждом шаге находится увеличивающая величину потока цепь. Поток увеличивается вдоль дуг этой цепи, пока она не станет насыщенной.
Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины a в вершину b назовем допустимой, если выполняется одно из следующих условий:
1. f(e) < c(e) и дуга согласованна
2. f(e) > 0 и дуга несогласованна
По увеличивающей цепи можно пустить поток величины Q, где Q = min{q(ei), 1 ? i ? l} и q(e) = {с(e) - f(e), если дуга согласованна, f(e), если дуга не согласованна}. Для того, чтобы увеличить величину потока сети на Q, необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.
В своей работе [3] Форд и Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным. Для нахождения увеличивающей цепи ими был предложен “Метод расстановки пометок”. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Как только сток оказался помеченным, мы можем говорить о существовании увеличивающей цепи из источника в сток. Метка, “наносимая” на вершины сети, содержит необходимый минимум информации, достаточный для того, чтобы восстановить эту цепь и определить величину, на которую можно изменить поток в ней. Вершина сети может находиться в одном из 3-х состояний: “непомеченная”, “помеченная” и “просмотренная”.
Этап 1. Расстановка меток.
Все вершины получают статус непомеченных.
Процедура расстановки меток.
Возьмем произвольный помеченный, но не просмотренный узел x. Пусть он имеет пометку [i, +, e(x)], где i - вершина из которой был помечен x; флаг, показывающий, что дуга (i,x) согласованна; e - величина потока, который можно пропустить по этой дуге. Рассмотрим все непомеченные смежные вершины y, такие что дуга (x, y) согласованна. Пометим вершину y меткой [x, +, e(y)], где e(y) = min{e(x) , c(x, y) - f(x, y)}. Затем рассмотрим все непомеченные смежные вершины y, соединенные с ней несогласованной дугой. Пометим их меткой [x, -, e(y)], где e(y) = min{e(x), f(y,x)}. Теперь все рассмотренные узлы y имеют статус помеченных, а узел x- просмотренный.
Эта общая для всех узлов сети процедура. Пометим источник меткой [~, ~, ?] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут - увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.
Этап 2. Изменение потока.
Процедура изменения потока дуги.
Возьмем узел x. Если он имеет метку [y, +, e], то увеличим поток по дуге (y, x) на e. Если он имеет метку [y, -, e], то уменьшим поток по дуге (y, x) на e. Если y не является источником, то вызовем процедуру для узла y.
Эта процедура, будучи вызвана для стока сети, позволяет пройти по найденной увеличивающей цепи к стоку, изменяя поток на ее дугах.
Следует особо отметить, что узлы, имеющие статус “помеченных”, больше не участвуют в процессе поиска увеличивающей цепи, весьма эффективно с вычислительной точки зрения.[1]
Алгоритм Форда-Фалкерсона гарантирует нахождение максимального потока только в сетях с целочисленными пропускными способностями. На практике “чистый” алгоритм Форда-Фалкерсона не применяется, т.к. оценка его производительности зависит от величины пропускных способностей дуг сети. Все дело в том, что в нем не дается каких либо правил выбора увеличивающей цепи. Рассмотрим сеть на рис. 1. Предположим, что реализован алгоритм, отдающий предпочтение увеличивающим цепям максимальной длины. В этом случае на первом шаге мы пустим дополнительный поток по цепи (0,1),(1,2),(2,3).
рис. 1 рис. 2
На втором шаге выберем цепь (0,2),(2,1),(1,3). Так как дуга (2,1) несогласованна, величина пущенного по ней потока будет вычитаться из величины потока, полученного на предыдущем шаге. Мы получили сеть (рис. 3) практически эквивалентную исходной.
рис. 3
Очевидно, что для нахождения максимального потока понадобиться 1000 итераций! В то время, как если бы мы на первом шаге выбрали цепь (0,1),(1,3), то результат был бы получен за одну итерацию! На практике, величина пропускных способностей часто зависит от единиц измерения, и может принимать огромные значения. Если же допустить иррациональные пропускные способности дуг, то можно привести пример невычислимой сети [4]. Величина потока в такой сети не превысит даже четверти истинного значения. Подобная неопределенность длилась не долго, уже в начале 70-х г. были предложены сразу 2 правила выбора увеличивающих цепей, которые существенно улучшают алгоритм Форда-Фалкерсона.
Алгоритм кратчайших увеличивающих цепей
Этот алгоритм получил наиболее широкое распространение. Он был опубликован в работе Эдмондса и Карпа [5] в 1969 и имеет полиномиальную оценку O(nm2).
Все дуги имеют единичную длину. В качестве увеличивающей цепи выбирается цепь наименьшей длины, при этом не учитывается пропускная способность дуг этой цепи.
Пусть q(u,v) - кратчайший путь из u в v. На каждом шаге работы алгоритма, для всех узлов v цепи {s, t} разностной сети, q(u,v) может только возрастать. Назовем дугу (u,v), принадлежащую цепи p разностной сети, критической, если пропускная способность этой дуги равна величине потока, пущенного вдоль p. После увеличения потока вдоль цепи p, эта дуга исчезнет из разностной сети. На каждом шаге определения цепи p хотя бы одна дуга будет критической. В [6] имеется доказательство того, что каждая дуга из E может быть критической не более |V|/2-1 раз. Т.к. мы имеем O(E) пар вершин, соединенных дугами в разностном графе, то общее число критических дуг будетO(EV). Каждая итерация алгоритма Форда-Фалкерсона выполняется за время O(E), следовательно, общая оценка алгоритма кратчайших цепей будет O(mn2).
На практике подобный алгоритм легко реализовать, используя поиск в ширину на первом этапе метода пометок Форда-Фалкерсона.
Алгоритм локально-максимального увеличения
Второй метод выбора увеличивающей цепи, предложенный Эдмондсом и Карпом в 1972 г. позволяет найти максимальный поток за O(nm2M(G)), где M(G) - . Хотя его трудоемкость и зависит логарифмически от пропускных способностей сети, на практике дает вполне приемлемые результаты. Согласно этому методу, поток изменяется вдоль цепи с наибольшей пропускной способностью. Вновь рассмотрим метод пометок. Добавим в метку поле p - приоритет узла. На этапе инициализации алгоритма все вершины имеют нулевой приоритет. Тогда припометки вершины y из x приоритет p будет равен max{p, p1}, где p - текущий приоритет вершины.
p1 = с(y) - e(y), если дуга (x, y) согласованна
p1 = -e(y), если дуга (x, y) несогласованна.
Процесс пометки вершин следует продолжать до тех пор, пока все вершины не получат статус просмотренных.
На втором этапе, при восстановлении пути из стока в источник, следует воспользоваться методами динамического программирования и выбрать путь, сумма приоритетов вершин которого максимальна.
В работе [7] показан пример оптимизации алгоритма, приводящий к оценке трудоемкости O(n2m M(G)).
Алгоритм Диница
Этот алгоритм, опубликованный в 1970 г., имел огромное значение. На протяжении 10 лет все достижения в решении задачи о максимальном потоке базировались на методе Диница.
Основная идея метода - алгоритм состоит из фаз, на которых поток увеличивается сразу вдоль всех кратчайших цепей определенной длины. Для этого на i-той фазе строится вспомогательная бесконтурная сеть (layered network). Эта сеть содержит все увеличивающие цепи, длина которых не превышает ki, где ki - длина кратчайшего пути из s в t. Величину ki называют длиной вспомогательной сети.
Рассмотрим работу алгоритма на i-той фазе:
Шаг 1. Построение вспомогательной сети.
С помощью поиска в ширину мы движемся из источника сети в сток по допустимым дугам, добавляя их в Sk и увеличивая k. Дуга u добавляется с ck(u) = c(u) - f(u). Как только достигнут сток сети, он помечается величиной k и k становится “фиксированной”. Мы продолжаем поиск в ширину, но он уже не ведется из вершин v, для которых q(s, v) ? k. Таким образом, вспомогательная сеть будет содержать подсеть исходной. Если поиск в ширину не достиг стока, то работа алгоритма прекращается. Если k больше (k может только увеличиваться) ki, то мы находимся на i+1 фазе с ki+1 = k.
Шаг 2. Поиск псевдомаксимального потока.
В построенной нами бесконтурной сети длины k ищется псевдомаксимальный поток. Под псевдомаксимальным потоком понимается такой поток f, для которого не существует увеличивающих цепей длины k. Найденный поток переносится в исходную сеть. Затем мы вновь переходим к первому шагу.
Для построения псевдомаксимального потока используется поиск в ширину (с ограничением на длину пути). Пусть на j-той итерации был найден путь из s в t. Пустим по этому пути поток fj. Это значит, что как минимум одна дуга вспомогательной сети является насыщенной. Удалим все насыщенные дуги. В результате могут образоваться “тупики”: вершины, из которых не выходит ни одна дуга (кроме стока), вершины, в которые не входит ни одна дуга (кроме источника) и изолированные вершины. Их также следует удалить со всеми инцидентными им дугами. Это в свою очередь может привести к образованию новых тупиков. Корректировка производится, пока во вспомогательной сети не останется ни одного тупика. Изменим пропускные способности оставшихся дуг по формуле ck(u) = ck(u) - fj(u).
рис. 4
На рисунке вершины 2 и 5 являются тупиками. После их удаления будут последовательно удалены все вершины сети.
Поиск fj следует продолжать до тех пор, пока вспомогательная сеть ? Ш. Очевидно, что псевдомаксимальный поток f = ? fj. Псевдомаксимальный поток можно хранить в какой-либо структуре, но на практике найденные потоки fj обычно сразу переносятся в исходную сеть S.
Заметим, что после нахождения fi и корректировки сети, поиск в ширину можно продолжать с ближайшей к s не подвергшейся изменениям дуги найденного пути.
После завершения работы Алгоритма исходная сеть будет содержать максимальный поток. Пример:
рис. 5.
Сеть с уже найденным с помощью алгоритма Диница максимальным потоком.
рис. 6.
Вспомогательная сеть на 1 фазе. k1 = 2.
рис.7.
Вспомогательная сеть на 2 фазе. k2 = 3. На этой сети хорошо видно, что псевдомаксимальный поток обычно не является максимальным.
рис.8.
Вспомогательная сеть на 3 фазе. k3 = 5.
Метод поразрядного сокращения невязок
В зарубежной литературе этот метод получил название capacity scaling. Он был рассмотрен Эдмондсом и Карпом в 1972 и независимо Диницом в 1973. Если с его помощью модифицировать алгоритм кратчайших увеличивающих цепей или алгоритм Диница, то можно получить оценки быстродействия O(m2 Log U) и O(mn Log U) соответственно, где U = max(Cij).
Возьмем достаточно большое целое K (т.н. масштаб). Пусть все пропускные способности дуг округлены с недостатком до ближайшего кратного числу K и формируют сеть CSk. Тогда при увеличении потока в этой сети, он будет возрастать на целое, кратное K. Таким образом, для построения потока мощности M требуется не более M/Kитераций. Как только в сети CSk найден максимальный поток, уточним пропускные способности дуг, выбрав K' и округлив их с недостатком до ближайшего кратного числу K'. Где K' < K. После корректировки сети CSk и потока f(u), получим сеть CSk' с потоком f'(u). Если K кратно K', то имеющийся поток останется целочисленным. Полученный на предыдущей итерации поток следует увеличить, чтобы он вновь стал максимальным. Подбирая, таким образом, масштаб, мы все более полно будем использовать пропускные способности дуг. В случае целочисленных пропускных способностей, максимальный поток будет получен после его увеличения в масштабе K= 1.
На практике выбирают K = log2U. На i-той итерации берется масштаб 2(K-i+1). В целочисленном случае для нахождения максимального потока достаточно K+1 итерации.
Алгоритм Карзанова
Карзанову в 1974г удалось, с помощью модификации алгоритма Диница, добиться оценки быстродействия O(n3). Им также впервые было введено понятие “предпотока”. Дадим следующие определения:
Путь Lv,t из вершины v в сток t называется блокированным, если он содержит хотя бы одну насыщенную дугу.
Вершина (дуга) блокирована, если блокирован любой проходящей через нее путь.
Поток f в Sk называется тупиковым, если блокирован источник s.
Предпотоком назовем поток g, удовлетворяющий 4-м условиям:
1. 0 ? g(u) ? ck(u), где u - дуга Sk сети, ck(u) - ее пропускная способность.
2. Для любой вершины v Vk \ {s, t}, div (v) ? 0.
3. если div (v) < 0, то v - g-блокирована.
4. источник s g-блокирован.
Согласно теореме, доказательство которой приведено в [7], если на i-ом этапе увеличить поток сети с помощью тупикового потока вспомогательной сети, то все кратчайшие увеличивающие пути длины ki будут исчерпаны, и алгоритм перейдет на следующий этап. Это значит, что последовательное построение псевдомаксимальных потоков в Sk сети, может быть заменено поиском тупикового потока. Далее рассматривается алгоритм построения тупикового потока в Sk сети.
Для работы необходимы следующие структуры данных:
A(v) - список исходящих из вершины v дуг. Строится для каждой вершины => n списков.
Q(v) - список “добавок” предпотока на дугах, входящих в вершину v. Добавка должна содержать информацию о величине добавки (q(u) > 0) и адрес (либо любой другой идентификатор) дуги u. Необходимо n таких списков. Список Q может содержать несколько добавок, относящихся к одной и той же дуге u.
g(u) - список из m элементов (одномерный массив), содержит текущие значения потока g на дугах u. Отметим, что g(u) = ? q(u) из Q(v), где v - конец дуги u.
Dv(v) - список из n элементов (одномерный массив), содержит div (v) для всех вершин v.
D - список дефицитных вершин.
Инициализация.
Дана Sk сеть. На всех дугах u исходящих из источника s увеличим поток g на величины, равные пропускным способностям этих дуг (изменяем g(u)). Для всех vсмежных с s Dv(v) = - ck(s, v), а в Q(v) заносится добавка q(u) = ck(u). Для остальных вершин Dv(v) = 0, списки Q(v) - пустые. D - пуст. Поток g на данный момент не является предпотоком, т.к. не удовлетворяет 3-му условию. Далее производится процедура “Достройки” (будет рассмотрена позднее), которая превратит g в предпоток и заполнит список D. Нахождение тупикового потока Sk сети - итеративный процесс. На каждой итерации выполняются 2 процедуры: “балансирование” и “достройка”. Достройка производится только в случае необходимости, балансирование - всегда. Тупиковый поток будет построен, как только список дефицитных вершин D станет пустым.
Балансирование.
Перед началом балансирования g - всегда предпоток. Балансирование производится на дефицитных вершинах D максимального ранга (максимально удаленных от источника s). Заметим, что по построению, вершины в списке D упорядочены по возрастанию рангов (за исключением случая, который будет оговорен позднее), поэтому, чтобы перебрать все дефицитные вершины максимального ранга, нужно просматривать элементы с конца списка D, до тех пор, пока ранг не изменится.
Балансирование вершины v заключается в получении div(v) = 0, с помощью изменения величины g на входящих в v дугах. Для этого берется элемент q(u) из Q(v), его значение необходимо уменьшить на y = min{q(u), -div(v)}. Если после уменьшения div(v) все еще < 0, то q(u) = 0. Удаляем q(u) (в [7] доказано, что можно и не удалять) изQ(v) и берем следующий элемент Q(v). Как только div(v) = 0, балансировка в вершине v прекращается (вершина v удаляется из D) и начинается балансировка следующей вершины. При изменении уменьшении q(u) также должны производится следующие изменения: g(u) := g(u) - y, Dv(v) := Dv(v) + y, Dv(v') := Dv(v') - y, где v' - вершина, из которой исходит дуга u. До уменьшения q(u), Dv(v') ? 0. Если Dv(v') было < 0, то v' уже есть в списке D и никаких дополнительных действий предпринимать не следует. Если Dv(v') было = 0, то теперь вершина v' “разбалансирована”. Подобные вершины называются источниковыми и дописываются в конец D. Это нарушает порядок следования вершин в D, но, т.к. все источниковые вершины имеют ранг на 1 меньший, чем вершины, подвергнувшиеся балансировке, а они в свою очередь, после балансировки будут удалены из D, то элементы в D вновь станут упорядоченными по возрастанию рангов. При реализации метода, необходимо следить, чтобы балансировка продолжалась с вершины, которая была последней в D до начала балансировки, а не с добавляемых к D источниковых вершин. Также удобно ввести переменную, хранящую адрес 1-й источниковой вершины в D.
Достройка.
Достройка необходима в том случае, если g не является предпотоком или в D содержатся источниковые вершины. Достройка производится последовательно в каждой вершине списка D, начиная с первой источниковой вершины до конца списка. Во время выполнения достройки в вершине, могут быть получены новые дефицитные вершины - они также дописываются в конец D и участвуют в достройке. Т.о. процедура достройки обрабатывает все источниковые и новые дефицитные вершины. При помещении в список новых дефицитных вершин, упорядоченность элементов по возрастанию рангов сохраняется.
Достройка в вершине. Пусть v - обрабатываемая вершина. Цель достройки - получение div(v) = 0, либо сделать ее блокированной. Для этого изменениются величиныg(u) для u A(v). Последовательно обрабатываем дуги u из A(v). Пусть u = (v, v'). Если A(v') пуст, то вершина v' блокирована => дуга u блокирована. В этом случае достройка в u не производится и u удаляется из A(v). Если же A(v') не пуст, то не известно, блокирована дуга u или нет. Увеличим g(u) на y = min{ck(u) - g(u), -div(v)}. Внесем изменения и в остальные структуры: Dv(v) := Dv(v) + y, Dv(v') := Dv(v') - y. Добавим q(u) = y в список Q(v'). Если div(v) до изменения была = 0, то теперь она стала новой дефицитной вершиной и должна быть занесена в D, если div(v) была < 0, то она уже содержится в D.
Если после увеличения g(u) div(v) < 0, то g(u) = ck(u) - дуга u становится g-блокированной, удаляется из A(v) и процедура обрабатывает следующую дугу из списка. Если же div(v) = 0, то в вершине v установлен баланс - вершина удаляется из D, достройка в этой вершине прекращается.
Т.к. при достройке предпотока в D заносятся только вершины, ранее ему не принадлежавшие, то рост списка D конечен.
Алгоритм Малхотри-Кумара-Махешвари
В 1978г Малхотри, Кумару м Махешвари (Malhotra, Pramodh Kumar, and Maheshwari) удалось с помощью модификации алгоритма Диница получить алгоритм с оценкойO(n3) и тем самым повторить результат Карзанова.
“Потенциалом” вершины сети (далее P(v)) назовем максимальное количество потока, которое может быть пропущено через вершину. Очевидно, что потенциал является минимумом из суммарной пропускной способности входящих в вершину дуг (Pi(v)) и суммарной пропускной способности исходящих дуг (Po(v)). Для источника и стока потенциал равен Pi(v) и Po(v) соответственно.
Изменим процедуру нахождения псевдомаксимального потока в Sk сети.
Для каждой вершины сети вычислим ее потенциал. До тех пор, пока Sk содержит вершины с ненулевым потенциалом, выполнятся следующее:
1. Поместим все вершины с нулевым потенциалом в стек. Пока стек не окажется пуст, извлекаем вершины из стека и удаляем их вместе с инцидентными им ребрами, уменьшая потенциалы смежных вершин. Если потенциал смежной вершины окажется равным 0, то она также помещается в стек.
2. Найдем вершину v с минимальным потенциалом p = P(v).
3. Построим поток из v в сток t величины p. Для этого увеличиваем поток на исходящих из v дугах, до тех пор, пока его величина не достигла p. Используются только согласованные допустимые дуги. Теперь в вершинах v' инцидентных дугам, по которым пустили поток, находится некоторая величина p'i. Величина p'i гарантированно может быть “продвинута” дальше, т.к. p'i ? p, а для v, p ? Pi(v). Для каждой такой вершины повторяем процедуру увеличения потока, пока величина достигшего стока потока не будет равна p. На практике эту процедуру удобно реализовать с помощью поиска в ширину.
4. Построим поток из v в источник s величины p аналогично предыдущему пункту.
5. Из 3 и 4 следует, что построенный в Sk поток является потоком из s в t. Перенесем его в исходную сеть, либо “запомним” в какой либо структуре. Скорректируем сеть аналогично процедуре из алгоритма Диница, изменяя потенциалы инцидентных удаляемым дугам вершин.
Поток, образованный объединением полученных на каждой итерации потоков, является псевдомаксимальным для Sk.
Алгоритм Галила-Наамада
Предложен в 1980г и имеет оценку O(nm*log2(N)). Данный алгоритм был также независимо рассмотрен Shiloach
Метод базируется на алгоритме Диница и в его основе лежит усовершенствование метода построения псевдомаксимального потока. Рассмотрим путь из s в t, найденный в Sk на i-той итерации:
рис. 9.
Пусть после увеличения потока в этой цепи, помеченные на рисунке дуги стали насыщенными (а как минимум одна насыщенная дуга в цепи появится). После корректировки сети эти дуги удаляются, и поиск пути из s в t продолжится из вершины, окрашенной желтым. Информация об остальных участках цепи будет утрачена, эти части могут быть заново пройдены - что не эффективно. Подобные участки Галил и Наамад назвали “Фрагментами пути”. Сохраняя информацию об этих фрагментах и используя ее для построения цепи из s в t, им удалось увеличить быстродействие алгоритма Диница.
Рассмотрим операции, определенные для фрагментов пути. Пусть PF1 и PF2 - два фрагмента пути. Обозначим s(PF) - начальную вершину пути PF, e(PF) - конечная вершина PF, v(PF) - множество внутренних вершин PF (v PF \ {s(PF), e(PF)}). Если e(PF1) = s(PF2), для фрагментов допустима операция объединения. Результатом будет являться PF = PF1PF2. В случае, когда e(PF1) = w v(PF2), PF2 может быть разделен на 2 фрагмента PF3 и PF4, где e(PF3) = w и s(PF4) = w. Затем PF1 и PF4 можно объединить. Для любой вершины сети v, может существовать только один фрагмент пути, для которого vv(PF), либо v = s(PF). Но могут иметься несколько фрагментов, оканчивающихся на эту вершину.
Для хранения информации о фрагментах пути и проведения операций над ними, используются специальные структуры - “2-3 деревья”. В рамках этой работы мы не будем их рассматривать. Разработка эффективных способов представления деревьев и сетей является отдельным направлением исследований. Использованные в алгоритме 2-3 деревья подробно описаны в [8].
Спустя некоторое время, совместно Слейтор и Тарян (Sleator and TarJan) предложили структуру данных, обеспечивающую еще большее быстродействие [9]. С помощью этой структуры оценка алгоритма Галила-Наамада может быть улучшена до O(nm log n).
Динамические деревья Слейтора-Тарьяна
Слейтор и Тарян в 1981г. разработали на основе деревьев, использованных в алгоритме Галила-Наамада, улучшенную структуру данных. Их динамические деревья позволяют производить операции слияния (link) и разделения (cut) за время O(log n). Модификации деревьев Слейтора-Таряна используются для повышения оценки быстродействия практически во всех современных алгоритмах.
Для хранения информации о различных путях в сети и быстрого изменения этой информации, предлагается воспользоваться лесом деревьев. Одна и та же вершина сети не может одновременно содержаться в двух деревьях. Деревья допускают над собой два вида операций - слияния (link) и разделения (cut).
Link(v, w) - соединяет две вершины из различных деревьев, добавляя дугу (v, w). В результате 2 дерева сливаются в одно.
Cut(v, w) - Разделяет дерево, содержащее дугу (v, w) на два, с помощью удаления дуги (v, w). Вершины v и w должны быть смежными вершинами одного дерева.
Следует различать корневые и свободные деревья. В случае корневых деревьев операция Link(v, w) разрешена, только если v - корень дерева. Результатом слияния будет дерево с корнем, равным корню дерева, которому принадлежала вершина w. Предполагается, что дуги корневого дерева ориентированы по направлению к корню, т.е. от потомка к родительскому узлу. Заявленная оценка быстродействия справедлива как для корневых, так и для свободных деревьев.
Для применения подобной структуры к сетевым задачам, вводятся также 5 дополнительных операций:
Root(v) - возвращает корень дерева, содержащего v.
Cost(v, w) - возвращает “стоимость” (вес) дуги (v, w), т.е. вещественной число.
Find_min(v) - возвращает дугу минимальной стоимости на пути из v к корню дерева, в котором находится v. Если этот путь не содержит дуг, возвращается специальноеnull значение. Если дуг минимальной стоимости несколько, результатом будет ближайшая к корню дуга.
Update(v, x) - увеличивает стоимость всех дуг пути из v к корню дерева, в котором находится v, на x. x - вещественное число.
Evert(v) - изменяет дерево, содержащее вершину v, делая v корнем этого дерева.
Операция Link модифицируется для трех параметров: Link(v, w, x) - отличие лишь в том, что добавляемой дуге (v, w) присваивается стоимость x.
Первых 6 операций достаточно для применения деревьев Слейтора-Таряна к задаче о поиске тупикового потока. Операция Evert необходима лишь в случае использования свободных деревьев.
рис. 10.
а). Операция Link в корневом дереве. b). Операция Cut в корневом дереве.
c). Операция Link в свободном дереве. d). Операция Cut в свободном дереве
Иллюстрации из [9].
Нахождение тупикового потока с помощью динамических деревьев.
Инициализация. Помещаем в нашу структуру все вершины сети (без дуг), получим множество “деревьев”, состоящих из одной изолированной вершины.
Шаг 1. Пусть v = root (s). Если v = t, перейдем к шагу 4 иначе к шагу 2.
Шаг 2. (v ? t). Если из вершины v не исходит ни одной дуги, перейдем к шагу 3. Иначе, выбираем дугу (v, w), выполняем Link(v, w, c(v, w)) и переходим к шагу 1.
Шаг 3. (все пути из v в t блокированы). Если v = s, прерываем работу алгоритма. Иначе, для всех входящих в v дуг (содержащихся в этом дереве) выполняем cut(u, v), и переходим к Шагу 1.
Шаг 4. (s и t в одном дереве, t = root(s), путь из s в t - увеличивающий поток путь). Пусть (v, w) = Find_min(s). (нашли дугу минимальной пропускной способности). Пусть cmin = cost(v, w). Выполняем Update(s, -cmin) и переходим к шагу 5.
Шаг 5. (удаление дуг с нулевой пропускной способностью). Пусть (v, w) = Find_min(s). Если cost(v, w) = 0, то cut(c, w) и выполняем шаг 5 заново. Иначе переходим к шагу 1.
После окончания работы цикла, максимальный поток определяется разницей пропускных способностей дуг до и после выполнения алгоритма. Результат будет получен за O(nmLogn).
Деревья Слейтора-Таряна (и их модификации) применяются не только для нахождения тупиковых потоков, они используются в задаче нахождения наиболее удаленного от корня общего предка для двух заданных вершин, задаче нахождения поддеревьев минимальной стоимости при различных условиях (для решения используются свободные деревья) и в симплекс методе решения сетевых задач.
Алгоритм Голдберга-Таряна
Опубликован в 1986г. Алгоритм основан на идее предпотоков Карзанова, но не использует поиск тупикового потока в фазах. Оценка быстродействия алгоритма:O(n3), но может быть улучшена до O(nmLog(n2/m)), если алгоритм реализован с использованием динамических деревьев Слейтора. Также имеется версия алгоритма для параллельных вычислений с оценкой O(n2Logn) на n процессорах. В основе алгоритма лежат 2 операции: наращивание потока (Push) и изменение метки вершины (Relabel), в связи с этим, метод примененный в алгоритме получил название Push-Relabel. Данный метод внес большой вклад в исследование проблемы максимального потока. Многие современные алгоритмы основаны на Push-Relabel методе.
Рассмотрим неориентированную сеть G. Дадим следующие определения:
Функция избытка:
e(v) = - div (v) = ? f(v',v) - ? f(v,v'').
Псевдопотоком назовем функцию f, удовлетворяющую ограничениям пропускных способностей дуг и антисимметричности. Антисимметричность означает что f(v, w) = - f(w, v). Понятие антисимметричности предложено Слейтором и служит двум целям. Во-первых, оно исключает возможность существование положительного потока как в направлении (u, v), так и в направлении (v, u). Во вторых, оно упрощает некоторые определения, например, закон сохранения потока.
Предпотоком является псевдопоток на пути из s в t, для всех вершин которого e(v) ? 0 (кроме s).
Под rf(v,w) будем понимать остаточную пропускную способность дуги (v, w). Gf - сеть остаточных пропускных способностей потока f.
Каждой вершине сети сопоставим метку d(v) ? 0, обладающую следующими свойствами: d(t) = 0, d(s) = n, для r(v, w) Gf d(v) ? d(w) + 1. Если d(v) < n, то под ней можно понимать дистанцию до стока в Gf, иначе d(v) - n - дистанция до источника Gf.
Назовем вершину активной, если она не является источником или стоком и имеет положительный избыток (e(v) > 0).
Рассмотрим базовые операции:
Push(v, w). Увеличивает поток из v в w на q, где q = min{e(v), r(v, w)}. Очевидно, что вершина v должна быть активной, дуга (v, w) не насыщенной, а d(v) = d(w) + 1.
Relabel(v). Обновление метки вершины v. Вершина должна быть активной, и для w с r(v, w) > 0 должно выполнятся d(v) ? d(w). Relabel устанавливает d(v) =min(d(w)+1| (v,w) Ef), где Ef - множество дуг сети остаточных пропускных способностей относительно потока f.
Push_Relabel(v).
Пока e(v) не станет нулевой или не изменится d(v) выполняем внутренний цикл:
Пусть (v, w) - текущая дуга в списке a(v). Рассмотрим 2 случая.
a). Операция Push применима к (v, w). В этом случае производим увеличение потока и, если вершина w стала активной, помещаем ее в конец очереди X.
б). Push не применима к (v, w). Тогда, если (v, w) не последняя дуга в a(v), то делаем текущей следующую дугу списка. Если же (v, w) последняя дуга, то выполняемRelabel(v) и выбираем текущей первую дугу в a(v). В [10] доказана применимость Relabel к v после обработки всех дуг a(v).
Общая логика работы алгоритма такова:
Инициализация.
В смежные источнику вершины v посылается поток величины c(s, v). Поток на остальных дугах нулевой. Смежные с источником вершины становятся избыточными, избыток в остальных вершинах отсутствует. Расставим метки: d(s) = n, для всех остальных вершин d(v) = 0.[1] Поместим все активные вершины в очередь X.[2] Также нам потребуются списки всех исходящих дуг a(v) для каждой вершины. В этих списках будет выбрана “текущая дуга” (при инициализации текущей дугой выбирается первая дуга в списке). Главный цикл.
До тех пор, пока очередь X не пуста, извлекаем вершину v из очереди и выполняем Push_Relabel. Проверим, не перестала ли вершина v быть активной. Если нет - добавляем ее в конец X. Переходим к следующей вершине очереди X.
Применение динамических деревьев в алгоритме Голдберга-Таряна.
Без использования деревьев Слейтора-Таряна алгоритм имеет оценку быстродействия O(n3), что повторяет достижение Карзанова. Рассмотрим набор корневых, не имеющих общих вершин деревьев. Каждой вершине сопоставим число g(v), которое может дополнительно принимать значение + ? и - ?. g(v) - это пропускная способность исходящей из v дуги. Пусть p(v) - множество предков вершины v, P(v) - смежный с v предок. Примем условие, что любая вершина v для самой себя одновременно и предок, и потомок. Введем следующие операции:
Root(v) - аналогична операции в деревьях Слейтора-Таряна.
Size(v) - возвращает число вершин в дереве, которому принадлежит v.
Value(v) - аналог процедуры Cost для дуг. Возвращает g(v).
Find_min(v) - возвращает ближайшего к корню предка w p(v), с минимальным g(w).
Update(v, x) - добавляет x к g(w), для каждого w p(v). (- ? + ? = 0).
Link(v, w) - соединяет деревья, которым принадлежат вершины v и w, делая v потомком w. Если v и w принадлежат одному дереву или v не является корнем, то процедура завершается, не изменяя деревьев.
Cut(v) - Делит дерево на два, удаляя дугу из вершины v к ее предку. Если v - корень, то процедура не применяется.
Динамические деревья используются для хранения текущих дуг вершин. Во время инициализации все вершины представляют собой набор корней деревьев без дуг.g(v) всех вершин = ?. Дуги дерева являются подмножеством текущих дуг вершин сети. В дерево могут быть добавлены только допустимые текущие дуги. Назовем текущую дугу (v, w) вершины v V \ {s, t} допустимой, если d(v) = d(w) + 1 и rf(v, w) > 0. Дуга (v, w) добавляется в дерево так, что w = P(v). Ограничим размер дерева числом k, где k = n2/m (объяснение подобного решения см. в [10]).
Опишем следующие процедуры:
1. Clear(v) - удаление всех дуг с нулевой пропускной способностью.
Пока Value(Find_min(v)) = 0 выполнять: u := Find_min(v); Cut(u); Update (u, + ?).
2. Send(v) - “проталкивает” избыток вершины v в корень дерева:
До тех пор, пока вершина v не стала корнем дерева, или избыток вершины не стал равен 0, выполняем Update(v, -q),где q = min{e(v), Value( Find_min(v) )} и Clear(v). Процедура Send применима только к активным вершинам.
3. TreePush_Relabel(v) - применима только если v активна и является корнем дерева. Рассмотрим текущую дугу (v, w) вершины v. Имеются 4 случая:
а.) Дуга допустима и Size(v) + Size(w) ? k. Тогда делаем v потомком w, выполняя Update(v, - ?) (чтобы получить g(v) = 0), Update(v, rf(v, w)) и Link(v, w). И “проталкиваем” поток: send(v)
б). Дуга допустима и Size(v) + Size(w) > k. Выполняем Send(w).
в). Дуга не допустима и не является последней в списке a(v). Выбираем следующую текущую дугу из списка.
г). Дуга не допустима и последняя в a(v). Выбираем текущей дугой первую дугу списка. Выполняем Cut(v, w). Для всех потомков u вершины v выполняем Update(u, ?). В завершение, вызываем Relabel(v).
Заменив в главном цикле процедуру Push_Relabel на TreePush_Relabel, мы получим алгоритм поиска максимального потока для динамического дерева.
В своей статье Голдберг и Тарян предложили также ряд эвристик, которые не влияют на асимптотическую оценку алгоритма, но могут увеличить его быстродействие на практике. Например периодическое обновление меток вершин в сети остаточных пропускных способностей, с помощью поиска в ширину из источника в сток и из стока в источник. Такой поиск позволит получить для вершины v расстояние до стока d(v, t) и до источника d(v, s). В качестве d(v) следует выбрать min{d(v, s) + n, d(v, t)}. Есть несколько вариантов выбора момента проведения этого уточнения. Например, через каждые k операций Relabel, или каждый раз, когда насыщается дуга, ведущая в сток, либо поток по исходящей из источника дуге окажется нулевым.
Благодаря “гибкости” своей реализации, возможности распараллеливания вычислений и высокому быстродействию на большинстве типов сетей, Push-Relabel методы получили широкое распространение на практике.
Алгоритм CHM
В 1989г Cheriyan, Hagerup & Mehlhorn предложили очень интересную модификацию алгоритма Голдберга-Таряна. В оригинальном алгоритме поток из одной вершины в другую перемещается по текущей допустимой дуге. После того, как текущая дуга станет недопустимой, необходимо выбрать следующую текущую дугу. Четкого правила выбора следующей текущей дуги не давалось.
В предлагаемом алгоритме рассматривается неориентированная сеть. Максимальный поток вычисляется в фазах с помощью “неполного” графа {V, E'}, где E'E. Дуги в этот вспомогательный граф добавляются по очереди, в порядке, позволяющем дуге стать насыщенной после добавления. Вместо функции избытка e(v), используется функция “явного” избытка e'(v) = max{e(v) - ? c(v, u), 0}. Функция явного избытка используется, что бы определить максимальную величину потока, который может быть “вытолкнут” из вершины v.
Так же как и в алгоритме Голдберга-Таряна, здесь используются динамические деревья, позволяющие быстро изменять поток в цепи. Все дуги в лесу должны быть допустимыми для операции Push. Каждый узел может иметь максимум одну исходящую дугу. Во время насыщения дуги, она удаляется с помощью операции Cut. Во время выполнения операции Relabel(v), все направленные в v дуги удаляются из дерева. При выборе для вершины новой допустимой текущей дуги, она добавляется в дерево с помощью Link.
Алгоритм не имеет ограничения k на размер структуры. Операция TreePush_Relabel может применяться не только к корню дерева.
Cheriyan, Hagerup & Mehlhorn удалось доказать, что в случае выбора допустимой дуги случайным образом, оценка быстродействия алгоритма с высокой степенью вероятности будет равна O(mn + (nLogn)2). Самым интересным является метод, с помощью которого была доказана подобная оценка.
Рассмотрим игру, игроками в которой являются алгоритм (игрок) и его “соперник”. Пусть дана сеть G = (V,E). Построим для нее “игровое поле” - двудольный граф G' = (U', V', E'), такой, что для каждой вершины w из V и для всех k от 1 до 2n-1, в этом графе вершины uw,k U' и vw,k-1 V'. Общее число вершин O(n2). Для всех дуг (w,w') из E, существуют 2n-1 их копии: (uw,k, vw',k-1) для k = 1, …, 2n-1.
Назначение ребра из каждого uw,k означает выбор алгоритмом текущей дуги для вершины w, при d(w) = k.
Поведение соперников связано с вычислением максимального потока следующим образом:
Когда вершине w присваивается метка k, все игровые дуги, инцидентные uw,k, кроме той, что является текущей допустимой, удаляются из G'. Когда метка w меняется с k на k+1 (в процедуре Relabel), мы должны удалить (процедурой cut) все входящие в w дуги из леса F. В игре, соперник игрока удаляет вершину vw,k, и получает очко за каждое назначенное ребро инцидентное vw,k. (ребра также удаляются). Т.е. каждое удаление ребра из F соответствует очку, получаемому соперником.
Когда дуга насыщается, соответствующая ему дуга в G' (с необходимыми значениями k) удаляется соперником. Т.е. удаление соперником дуги (ход edge-kill) соответствует приведшей к насыщению операции Push.
Когда игрок (алгоритм) выполняет переназначение дуги, в алгоритме поиска максимального потока происходит смена текущей дуги. Старая текущая дуга должна быть удалена из F, что опять же приносит очко сопернику.
...Подобные документы
Шифрование - широко используемый криптографический метод сохранения конфиденциальности информации. Описание схемы шифрования и расшифрования. Структура алгоритмов на основе сети Фейстеля. Скриншоты работающей программы. Скорость работы алгоритмов.
курсовая работа [545,2 K], добавлен 29.11.2010Анализ и практическая реализация использования администрирования и мониторинга сети на предприятии. Процесс создания карты сети в программе LANState. Сетевые программы для сисадминов, программы мониторинга сети. Описание локальной вычислительной сети.
курсовая работа [3,6 M], добавлен 15.02.2017Технология настройки распределённой беспроводной сети в домашних условиях с использованием двух точек беспроводного доступа: выбор оборудования, определение архитектуры сети. Средства безопасности беспроводной сети, процедура ее взлома с протоколом WEP.
статья [152,4 K], добавлен 06.04.2010Сущность и классификация компьютерных сетей по различным признакам. Топология сети - схема соединения компьютеров в локальные сети. Региональные и корпоративные компьютерные сети. Сети Интернет, понятие WWW и унифицированный указатель ресурса URL.
презентация [96,4 K], добавлен 26.10.2011Принцип деятельности ООО "МАГМА Компьютер". Особенности предметной области. Цели создания компьютерной сети. Разработка конфигурации сети. Выбор сетевых компонентов. Перечень функций пользователей сети. Планирование информационной безопасности сети.
курсовая работа [2,3 M], добавлен 17.09.2010Локальные вычислительные сети. Пропускная способность сети. Определение загруженности сети. Выбор физической среды передачи данных. Распределение адресного пространства. Проверочный расчет времени двойного оборота. Пассивное сетевое оборудование.
курсовая работа [2,9 M], добавлен 17.02.2012Особенности проектирования локальной сети для учебного учреждения на основе технологии Ethernet, с помощью одного сервера. Описание технологии работы сети и режимов работы оборудования. Этапы монтажа сети, установки и настройки программного обеспечения.
курсовая работа [1,9 M], добавлен 16.02.2010Определение понятия и сущности сети Интернет. История возникновения компьютерной сети. Характеристика оптоволоконных и беспроводных линий связи, радиоканалов и спутниковых каналов. Протокол, используемый компьютерами для обмена данными при работе в сети.
презентация [3,0 M], добавлен 19.02.2015Настройка телекоммуникационного оборудования локальной вычислительной сети. Выбор архитектуры сети. Сервисы конфигурации сервера. Расчет кабеля, подбор оборудования и программного обеспечения. Описание физической и логической схем вычислительной сети.
курсовая работа [1,3 M], добавлен 22.12.2014Понятие и основные характеристики локальной вычислительной сети. Описание типологии "Шина", "Кольцо", "Звезда". Изучение этапов проектирования сети. Анализ трафика, создание виртуальных локальных компьютерных сетей. Оценка общих экономических затрат.
дипломная работа [990,2 K], добавлен 01.07.2015Разработка логической структуры сети и формирование групп пользователей сети виртуальных сетей. Разбиение сети на сегменты. Маршрутизация в сетях. Автоматизация настроек маршрутизации. Построение отказоустойчивой сети фармацевтической организации.
дипломная работа [3,3 M], добавлен 07.02.2016Изучение понятия и особенностей построения компьютерной сети с файл-сервером. Проект структурной схемы сети и схемы сети на плане здания. Удаленный доступ и удаленное управление сервером. Сети с шинной топологией. Характеристика требуемого оборудования.
курсовая работа [1,5 M], добавлен 18.03.2013Разработка проводной локальной сети и удаленного доступа к данной сети с использованием беспроводной сети (Wi-Fi), их соединение между собой. Расчет времени двойного оборота сигнала сети (PDV). Настройка рабочей станции, удаленного доступа, сервера.
курсовая работа [2,0 M], добавлен 10.11.2010Применение сетевых технологий в управленческой деятельности. Понятие компьютерной сети. Концепция открытых информационных систем. Преимущества объединения компьютерных сетей. Локальные вычислительные сети. Глобальные сети. Международная сеть INTERNET.
курсовая работа [38,1 K], добавлен 16.04.2012Классификация компьютерных сетей. Назначение компьютерной сети. Основные виды вычислительных сетей. Локальная и глобальная вычислительные сети. Способы построения сетей. Одноранговые сети. Проводные и беспроводные каналы. Протоколы передачи данных.
курсовая работа [36,0 K], добавлен 18.10.2008Нейронные сети и оценка возможности их применения к распознаванию подвижных объектов. Обучение нейронной сети распознаванию вращающегося трехмерного объекта. Задача управления огнем самолета по самолету. Оценка экономической эффективности программы.
дипломная работа [2,4 M], добавлен 07.02.2013Назначение и классификация компьютерных сетей. Обобщенная структура компьютерной сети и характеристика процесса передачи данных. Управление взаимодействием устройств в сети. Типовые топологии и методы доступа локальных сетей. Работа в локальной сети.
реферат [1,8 M], добавлен 03.02.2009Понятие локально-вычислительной сети и ее преимущества. Основные виды топологий. Типы серверов в компьютерной сети. Характеристика модели OSI. Технические и программные характеристики рабочих станций. Аппаратные средства для поиска неисправностей в сети.
дипломная работа [1,6 M], добавлен 14.06.2015Функциональная модель процесса проектирования сети. Технико-экономическое обоснование разработки сети. Проектирование структурной схемы и перечень функций пользователей сети. Планирование информационной безопасности. Расчет капитальных вложений.
практическая работа [345,0 K], добавлен 09.06.2010Прогнозирование на фондовом рынке с помощью нейронных сетей. Описание типа нейронной сети. Определение входных данных и их обработка. Архитектура нейронной сети. Точность результата. Моделирование торговли. Нейронная сеть прямого распространения сигнала.
дипломная работа [2,7 M], добавлен 18.02.2017
