Практическая работа №7 Задачи синтеза сетей

Практическая работа №7

с курса Цифровые системы коммутации

на тему: Задачи синтеза сетей

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

Задача поиска кратчайшей связующей сети (остовное дерево)

При проектировании сетей часто возникает задача нахождения минимальной связующей сети (по стоимости, по длине линий). Например, для получения нижней оценки стоимости структуры кабельной канализации. Исходные данные содержат структуру графа ситуационных трасс — места расположения пунктов связи и связывающих их участков, по которым могут проходить линии кабельной канализации, задана их числовая характеристика (вес — протяженность, стоимость). Вес может быть оценен как сумма стоимости строительства самого участка плюс стоимость единицы кабеля, умноженного на длину участка. Требуется найти структуру линий, соединяющих все пункты связи, при этом сумма весов участков линий была бы минимальна. Такая практическая задача сводится к решению задачи на графе, которая называется "задача нахождения минимального остовного дерева". Для решения этой задачи существуют эффективные алгоритмы – алгоритм Прима и алгоритм Краскала.

"Задача нахождения минимального остовного дерева" применяется при решении следующих прикладных задач:

1. Построение оптимальной схемы прокладки кабельных линий.

2. Оценка надежности сети.

3. Задача Штейнера (построение минимального остовного дерева на подмножестве вершин).

4. Определение нижней оценки для "задачи коммивояжера" (кольцевая структура, связывающая все вершины).

Минимальным остовным деревом называется остовное дерево, у которого сумма весов ребер минимальна.

Задача поиска минимального остовного дерева

Задан граф ситуационных трасс G(V,E), где V— множество пунктов связи, E — множество участков линий связи ({e_ij }). Для каждого участка e_ij задан его вес с(e_ij), равный стоимости строительства линии связи или длине этой линии.

Найти минимальное остовное дерево T, для которого:

S с(e_ij) _—> min

e_ij Î T

Для решения поставленной задачи используются алгоритм Краскала или алгоритм Прима.

Алгоритм Краскала ("жадный алгоритм").

В ходе алгоритма будет формироваться множество T — структура остовного дерева в виде массива, введенного в главе 2, которое исходно является пустым (T ={Æ}).

- Упорядочим множество ребер E по возрастанию весов ребер.

- Образуем цикл по множеству ребер.

- На каждом шаге выбираем ребро с минимальным весом.

- Если добавление этого ребра в дерево не приводит к образованию цикла, то включаем ребро в дерево Т.

- Цикл продолжать до тех пор, пока число ребер в дереве меньше (n-1).

Алгоритм Краскала удобнее программировать с использованием структуры данных типа "список ребер" (в виде массивов IU, OU,L в главе 2), который нужно упорядочить по возрастанию весов ребер.

Алгоритм Краскала имеет трудоёмкость, равную (m*log m) операций.

Пример построения остовного дерева с использованием алгоритма Краскала приведен на рисунке 9.

Рис. 9 – Пример построения основного дерева по алгоритму Краскала

Алгоритм Прима (алгоритм "ближайшего соседа")

Шаг 1. Алгоритм начинает работу с произвольной вершины, которая включается в дерево Т.

Шаг 2. Каждой вершине х_i, не принадлежащей Т присваиваются пометки (х_j, с_ij), где х_j – ближайшая смежная с х_i вершина дерева Т, а с_ij –вес ребра e(х_i,х_j). Если у вершины х_i нет смежных c вершинами дерева вершин, то ей присваивается пометка (-1, ∞).

Шаг 3. Выбирается вершина с наименьшей пометкой и включается в дерево Т.

Шаг 4. Если все вершины включены в дерево, то конец алгоритма.

Иначе, перейти на шаг 2.

Алгоритм Прима удобнее программировать с использованием структуры данных типа "структура смежности" в виде массивов UK, FO, LF.

Алгоритм Прима имеет трудоёмкость, равную (n²) операций и считается более эффективным для полных графов или графов с большим числом ребер.

Пример построения остовного дерева с использованием алгоритма Прима приведен на рисунке 10.

С уважением ИЦ "KURSOVIKS"!