Построение аппроксимирующего графа

Шаг 1. Вычислить по алгоритму Дейкстра кратчайшие пути между всеми парами вершин из множества X'. Алгоритм реализуется следующим образом:

- выбираем вершину (РАТС) и находим вершины, смежные с ней. Присваиваем каждой найденной вершине пару чисел, состоящую из № корневой (выбранной) и длины соответствующего ребра. Для остальных вершин графа сопоставляют пару (0, );

- из множества неотмеченных вершин найдем вершину с минимальным весом, включаем ее в дерево кратчайших путей и отмечаем ее. Далее, уже для вновь отмеченной вершины находим смежные с ней. Найденной вершине (смежной) присваиваем вес минимальный из двух возможных: либо уже существующий, либо вес, полученный из суммы длины ребра с весом предыдущей вершины; так необходимо повторять до тех пор, пока все вершины не будут просмотрены и отмечены.

Шаг 2. Построить полный граф G'=(X\ £/'), У которого множество

вершин совпадает с множеством вершин X'. Множество ребер соединяет все пары вершин по принципу каждая с каждой. Для каждого ребра uij положить

его вес равным длине кратчайшего пути из Xi в Xj в исходном графе G,

полученном на шаге 1.

Шаг 3. На полученном графе можно решать задачу коммивояжера, то есть найти цикл минимального веса, проходящий по всем вершинам X'.

Шаг 4. Получив структуру цикла в графе G', выделить кратчайшие пути в

графе G, соответствующие ребрам полученного цикла.

Методы решения «Задачи коммивояжера».

Рассмотрим алгоритмы получения верхней и нижней оценок для «Задачи

коммивояжера» (ЗК).

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

суммарного веса КОД. Верхняя оценка цикла в ЗК может быть получена с использованием стратегии «иди в ближайший». Опишем подробнее этот алгоритм.

Шаг 1. Выбрать исходную вершину в графе G’ и считать ее текущей вершиной строящегося нового цикла.

Шаг 2. Найти ближайшую вершину к текущей вершине относительно длины ребра и сделать ее текущей. Увеличить вес цикла на длину ребра.

Шаг 3. Если не все вершины включены в цикл, то шаг 2 повторяется. Если в цикл включены все вершины графа, то запомнить суммарный вес ребер, включенных в цикл. Если вес полученного цикла меньше предыдущего решения, считать его наилучшим.

Шаг 4. Если не все вершины графа просмотрены как исходные вершины циклов, то перейти на шаг 1, иначе цикл, имеющий минимальный вес является верхней оценкой для ЗК.

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

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

 

Верхняя оценка цикла в ЗК может быть получена с использованием стратегии «иди в ближайший». Опишем подробнее этот алгоритм.

Шаг 1. Выбрать исходную вершину в графе G’ и считать ее текущей вершиной строящегося нового цикла.

Шаг 2. Найти ближайшую вершину к текущей вершине относительно длины ребра и сделать ее текущей. Увеличить вес цикла на длину ребра.

Шаг 3. Если не все вершины включены в цикл, то шаг 2 повторяется. Если в цикл включены все вершины графа, то запомнить суммарный вес ребер, включенных в цикл. Если вес полученного цикла меньше предыдущего решения, считать его наилучшим.

Шаг 4. Если не все вершины графа просмотрены как исходные вершины циклов, то перейти на шаг 1, иначе цикл, имеющий минимальный вес является верхней оценкой для ЗК.

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

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


ЛИТЕРАТУРА

1. Гольдштейн Б.С., Соколов В.А. Автоматическая коммутация: учебник для студ. сред. проф. образования. - М: Издательский центр «Академия». 2007.

2. Берлин А.Н. Коммутация в системах и сетях связи - М: Эко-Трендз,

2006.

3. Крук Б.И., Попантонопуло В.Н., Шувалов В.П. Телекоммуника

ционные системы и сети: Учебное пособие. В 3 томах. Том 1 - современные технологии. Под ред. профессора Шувалова В.П. - Изд. 3-е. испр. и доп. - М.: Горячая линия - Телеком. 2003. v

4. Катунин Г.П., Мамчев Г.В., Попантонопуло В.Н., Шувалов В.П. Телекоммуникационные системы и сети: Учебное пособие. В 3 томах. Том ~: под ред. профессора Шувалова В.П. - Изд. 2-е, испр. и доп. - М.: I орячая линия -Телеком, 2004.

5. Величко Е. Субботин В. Шувалов, Ярославцев Ф. Телекоммуникационные системы и сети, т. 3. - М: Горячая линия - Телеком, 2005.

6. Тихвинский В.О., Терентьев С.В., Юрчук А.Б. Сети мобильной связи

LTE технологии и архитекту ра.- Москва: «Экотрендз», 2010. 1

7. Прозоров В.М. Общеканальная система сигнализации А® 7: Учебное пособие хля вузов. - М: Горячая линия-Телеком, 2008 .

8. Корякин-Черняк С.Л. Абонентские телефонные аппараты. Изд. 5-е, перераб. - СПб: Наука и техника. 2003.

9. Дж. Беллами. Цифровая телефония. Пер. с англ. - М.: Эко-Трендз ,2004.

10. Данилов В.И. Сотовые телефонные сети стандарта С8. -М.: Учебн. пособие. - СПб.: СП6ГУТЛ996.

11. Гольдштейн Б.С. Системы коммутации.- C-Пб.: БХВ-Петербург,2003.

12.

I
Гольдштейн Б. С. Сигнализация в сетях связи. - Москва: «Ралио и связь». 1997 г.

Интернет-ресурсы:

1. www.minsvyaz.ru Официальный сайт Министерства информационных технологий и связи.

2. www.sotovik.ru Информационный сайт, посвященный телекоммуникациям: обзоры рынка, новости операторов.

3. www.telecomru.ru Экспертный портал «Телекоммуникаций России».

4. –независимое сетевое СМИ

5. www.comnews.ru Новости рынка телекоммуникаций России и СНГ.

6. www.mobail-review.com Сайт, посвященный мобильным устройствам и технологиям, новостям операторов связи, рекламным акциям.