8.3. Методы анализа и синтеза сетей

Задачи анализа относятся к случаям, когда задана структура и характеристики элементов сети, а требуется определить характеристики обслуживаемых потоков. Или, наоборот, заданы характеристики потоков, а необходимо определить потребности в каналах.

Задачи синтеза связаны с построением сети, с поиском лучших структур, алгоритмов обмена информацией. Все эти задачи относятся к классу оптимизационных, когда осуществляется поиск лучшего решения.

Процесс решения оптимизационных задач складывается из ряда этапов:

1. Изучение объекта. Надо понять исследуемый объект, разобраться в происходящих в нем процессах, выделить необходимые характеристики, взаимосвязи.

2. Описательное моделирование. Осуществляется словесная формулировка (фиксация) основных связей и зависимостей между характеристиками процесса с точки зрения оптимизационного критерия.

3. Математическое моделирование. Перевод описательной модели на формальный математический язык. Все условия записываются в виде уравнений, неравенств (системы ограничений). Любое решение этой системы называется допустимым решением. Критерий записывается в виде функции, называемой целевой. Процесс оптимизации состоит в отыскании на множестве допустимых решений максимального или минимального значения целевой функции.

4. Выбор (или создание) метода решения задачи. После того как задача записана в математической форме, ее прикладная специфика уже не интересует. Главное внимание обращается на математическую структуру.

5. Выбор или написание программы для решения задачи на ЭВМ. Подавляющая часть сетевых задач из-за большого числа переменных и зависимостей между ними могут быть решены в разумные сроки только с помощью ЭВМ. Для решения их следует составить программу, реализующую выбранный метод решения, или использовать уже готовую, «стандартную» программу из библиотеки программ, если таковые есть.

6. Решение задачи на ЭВМ. Вся необходимая информация для решения задачи вводится в память машины вместе с программой. ЭВМ производит необходимую обработку в соответствии с программой и исходными данными. Результат выдается человеку в удобной для него форме.

7. Анализ полученного решения. Анализ двух видов: 1) формальный (математический), когда проверяется соответствие полученного решения построенной математической модели, и 2) содержательный (технологический, экономический и т.п.), когда проверяется соответствие полученного решения тому объекту (процессу), который моделировался. В результате такого анализа в модель могут быть внесены изменения или уточнения.

Решение многих задач анализа сетей начинается с определения путей между узлами сети. Одним из наиболее удобных и легко поддающихся машинизации способов определения путей является построение дерева путей. Оно (дерево путей) позволяет определить все пути от одного наперед заданного узла ко всем остальным узлам сети. Перечень путей удобно записывать в виде таблицы путей.

Существуют три стандартных алгоритма решения задач отыскания кратчайшего пути: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела. Первые два алгоритма находят кратчайшие пути от данного узла-источника ко всем другим узлам (или, эквивалентно, от всех узлов к данному узлу адресату),а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам.

Алгоритм Беллмана-Форда

Предположим, что узел 1 является узлом-источником и требуется найти длины кратчайших путей от узла 1 до каждого другого узла сети.

Основная идея алгоритма Беллмана-Форда состоит в том, чтобы сначала найти длины кратчайших путей при условии, что пути содержат не более одной дуги, затем длины кратчайших путей при условии, что пути содержат не более двух дуг и т.д. Кратчайший путь при условии, что путь содержит не более h дуг(ветвей),будет называться кратчайшим (≤ h) путём.

Пусть - длина кратчайшего (≤ h) пути от узла 1 до узла i. Будем считать, что =0 для всех h, а ∞, если отсутствует дуга (i,j).

Алгоритм Беллмана-Форда состоит в следующем.

Вначале ∞ для всех i≠1.

При каждом последующем h≥0

для всех i≠1.

Рис. 8.5 иллюстрирует работу алгоритма

8

1

У зел- 1 2 4 2 Длины дуг указаны

и сточник 4

2

∞

Кратчайшие пути,

использующие не более одной дуги.

∞

Кратчайшие пути,

использующие не более двух дуг.

Кратчайшие пути,

использующие не более трёх дуг.

Итоговое дерево

кратчайших путей.

Рис.8.5

Число операций алгоритма в худшем случае равно N-1,каждая операция должна быть проведена для N-1 узла, а для каждого узла минимизация осуществляется самое большее по N-1 переменной. Таким образом, в худшем случае объём вычислений записывается в виде 0( ),где N – число узлов в сети.

Алгоритм Дийкстра

Этот алгоритм требует, чтобы длины всех путей были положительны(это выполняется в сетях передачи данных).Объём вычислений в худшем случае для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда. Основная идея алгоритма состоит в том, чтобы отыскивать кратчайшие пути в порядке возрастания длины пути. Кратчайшим из всех кратчайших путей от узла 1 является путь, состоящий из одной дуги, соединяющий узел 1 с ближайшим соседним узлом. Следующим кратчайшим среди кратчайших путей должен быть либо путь из одной дуги к следующему ближайшему соседу узла 1,либо кратчайший путь из двух дуг, проходящей через узел, выбранный на первом шаге, и т.д. Для формального описания алгоритма каждый узел i имеет метку ,означающую оценку длины кратчайшего пути от узла 1.Когда оценка становиться неизменной, считается, что узел окончательно помечен. Множество окончательно помеченных узлов обозначим через P. Узел, который будет добавлен на очередном шаге к P, является ближайшим к узлу 1 среди всех узлов, ещё не вошедших в P, так как кратчайшее расстояние получается минимизацией по j P величины .Вычислительная сложность алгоритма будет порядка 0( ).

Рис.8.6 иллюстрирует работу алгоритм Дийкстра, а также алгоритма Беллмана-Форда.

3

1 2

1 1

4 4

1

Беллман-Форд

Дийкстра

=4 =3 =3

=6 =5

=4 =2 =3 =2 =3 =2

P={1,2} P={1,2,5} P={1,2,3,4,5}

Рис. 8.6

Формально алгоритм работает следующим образом.

Сначала P={1}, =0 и для j≠1.

Шаг 1(поиск следующего ближайшего узла).Найти i P такой, что

Положить P:=P {i}.Если P содержит все узлы, то на этом работа алгоритма заканчивается.

Шаг 2(обновление меток).Для всех j P положить .

Перейти к шагу 1.

Алгоритм Флойда-Уоршела

Этот алгоритм в отличии от предыдущих двух находит кратчайшие пути сразу для всех пар узлов. Если в алгоритме Беллмана-Форда итерируется число дуг в пути, а в алгоритме Дийкстра – длина пути, то в алгоритме Флойда-Уоршела итерируется множества узлов, которые допускается иметь в качестве промежуточных узлов на путях. Как и оба других алгоритма. Алгоритм Флойда-Уоршела начинается с расстояний из одной дуги (т.е. без промежуточных узлов),выбранных в качестве исходных оценок для длин кратчайших путей. Затем вычисляются кратчайшие пути с тем ограничением, что промежуточным узлом может быть только узел 1,затем с ограничением, что промежуточными узлами могут быть только узлы 1 и 2 и т.д.

Для более строгого описания алгоритма обозначим через

Длину кратчайшего пути от узла i к узлу j при ограничении, что только узлы 1,2,…, n могут использоваться в качестве промежуточных узлов на пути. Алгоритм при этом работает следующим образом.

Сначала = для всех i,j,i≠j.

Для n=0,1,…,N-1,

для всех i≠j.

Объём вычисления по данному алгоритму оценивается величиной 0( ),т.е. он такой же, как и алгоритм Дийкстра повторённого для всех узлов, выбранных в качестве источника.