Пример: Транспортная логистика
Я ищу:
На главную  |  Добавить в избранное  

Коммуникации и связь /

Основы построения телекоммуникационных систем

←предыдущая  следующая→
1 2 



Скачать реферат


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

КАФЕДРА «СЕТИ СВЯЗИ»

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Основы построения телекоммуникационных сетей»

Выполнил Принял

ст. гр. ИСС-01-1

Захарцов А.А. ______________

Харьков 2003

Соответственно номеру зачетной книжки выберем Кировоградскую область, т.к. она соответствует №17, а также запомним p=0,817.

Выберем десять городов, соответствующие нашей области:

1. Кировоград

2. Бобринец

3. Долинская

4. Новоукраинка

5. Новомиргород

6. Каменка

7. Знаменка

8. Александрия

9. Чигирин

10. Кривой рог

1 СИНТЕЗ ТОПОЛОГИИ СЕТИ ЭЛЕКТРОСВЯЗИ МЕТОДОМ М - СТРУКТУР

Составим матрицу расстояний для нашего графа:

Рисунок 1.1 – Граф сети

1 2 3 4 5 6 7 8 9 10

1 0 79 60 71 57 68 39 61 102 120

2 79 0 43 64 0 0 94 154 0 142

3 60 43 0 0 0 0 51 0 0 58

4 71 64 0 0 51 0 0 0 0 0

5 57 0 0 51 0 69 101 0 103 0

6 68 0 0 0 69 0 60 0 48 0

7 39 94 51 0 101 60 0 35 87 0

8 61 154 0 0 0 0 35 0 91 150

9 102 0 0 0 103 48 87 91 0 0

10 120 142 58 0 0 0 0 150 0 0

В соответствии с алгоритмом Прима сначала выписывается первая строка матрицы без первого столбца, что соответствует организации связи от первой вершины и соответствует организации связи от первой вершины (центрального пункта) к остальным - м ( ):

2 3 4 5 6 7 8 9 10

79 60 71 57 68 39 61 102 120

Выбираем в этой строке минимальный элемент . Далее вычеркиваем соответствующий ему 7-й столбец матрицы и, двигаясь по 7-й строке, сравнивается значение приведенных в ней элементов с их значениями в первой строке без первого и 7-го столбцов. Если значение элемента 7- й строки в соответствующем столбце оказывается меньше значения, указанного в первой строке, то эти значения меняются местами. Если наименьшим будет значение в первой строке, то замена не производится. Таким образом формируется следующая строка:

2 3 4 5 6 8 9 10

79 51

(7) 71 57 60

(7) 35

(7) 87

(7) 120

При этом цифрой 7 в скобках обозначены те значения длин, которые взяты из седьмой строки.

Вновь выбираем минимальный элемент строки . Действуя аналогично предыдущему, получаем новую строку:

2 3 4 5 6 9 10

79 51

(7) 71 57 60

(7) 87

(7) 120

Выбираем минимальный элемент строки . Ниже показан дальнейший процесс поиска:

2 4 5 6 9 10

43

(3) 71 57 60

(7) 87

(7) 58

(3)

4 5 6 9 10

64

(2) 57 60

(7) 87

(7) 58

(3)

4 6 9 10

51

(5) 60

(7) 87

(7) 58

(3)

6 9 10

60

(7) 87

(7) 58

(3)

6 9

60

(7) 87

(7)

9

48

(6)

В соответствии с алгоритмом Прима рассчитаем кратчайшее связное дерево (КСД). Оно будет содержать ребра: L1,7, L7,8, L7,3, L3,2, L1,5, L5,4, L3,10, L7,6, L6,9, общей длиной 442 единицы.

1 2 3 4 5 6 7 8 9 10

1 0 0 0 0 57 0 39 0 0 0

2 0 0 43 0 0 0 0 0 0 0

3 0 43 0 0 0 0 51 0 0 58

4 0 0 0 0 51 0 0 0 0 0

5 57 0 0 51 0 0 0 0 0 0

6 0 0 0 0 0 0 60 0 48 0

7 39 0 51 0 0 60 0 35 0 0

8 0 0 0 0 0 0 35 0 0 0

9 0 0 0 0 0 48 0 0 0 0

10 0 0 58 0 0 0 0 0 0 0

Структура такой сети представлена на рис. 1.2.

Рисунок 1.2 - Структура КСД

Выберем 5 городов, из нашей матрицы и составим для нее матрицу расстояний, перенумеровав города снова.

1. Кировоград

2. Новомиргород

3. Знаменка

4. Каменка

5. Чигирин

Рисунок 1.3 - Матрица расстояний графа

1 - й шаг. Выполняем сначала редукцию строк текущей матрицы расстояний. Для этого в каждой строке определяем минимальный элемент и найденное значение вычитаем из элементов соответствующей строки. Результаты выполнения редукции строк в виде матрицы приведены на рис. 1.4, где дополнительный вектор - столбец содержит вычитаемые при редукции константы.

Рисунок 1.4 - Редуцированная по строкам матрица расстояний на 1 - м шаге алгоритма

Затем выполняем редукцию столбцов, результаты которой в виде матрицы приведены на рис. 1.5, где дополнительный вектор - строка содержит вычитаемые при редукции константы. Значение элемента, расположенного на пересечении вектора - столбца и вектора - строки , равно сумме всех вычитаемых констант: = 249. Это значение является нижней границей длин всех маршрутов на данном шаге: =249.

Рисунок 1.5 - Редуцированная матрица расстояний на 1-м шаге алгоритма

Рисунок 1.6 - Начальный узел дерева решений

По редуцированной матрице расстояний далее определяем минимальные ненулевые значения ее строк и столбцов, которые записываем соответственно в виде вектора - столбца и вектора - строки . Матрица вместе с этими векторами показана на рис. 1.7.

Рисунок 1.7 - Редуцированная матрица и значения минимальных ненулевых элементов для 1-го шага алгоритма

Соответствующие элементам векторов и значения вторичных штрафов для различных звеньев или пар вершин с нулевыми значениями расстояний между ними приведены в табл. 1.1.

Таблица 1.1 - Вторичные штрафы на 1 - м шаге алгоритма

32

41

51

Как видно из табл. 1.1, максимальное значение равно 51. Выбирая звено , можно получить выигрыш в расстоянии, равный 51, т.е. больший, чем при выборе любого другого звена, за исключением звеньев , . Следовательно, в качестве базового звена на 1 - м шаге ветвления выбирается звено , а , Нижней границей длин маршрутов из подмножества на следующем (2 - м шаге) является величина .

Следовательно, модифицированная матрица расстояний после вычеркивания 4 -й строки и 5 -го столбца, а также замены элемента на пересечении 5 -й строки и 4 -го столбца матрицы на имеет вид, приведенный на рис. 1.8.

Рисунок 1.8 - Текущая матрица расстояний для 2-го шага алгоритма

2 - й шаг. Выполняем сначала редукцию строк текущей матрицы расстояний. Для этого в каждой строке определяем минимальный элемент и найденное значение вычитаем из элементов соответствующей строки. Результаты выполнения редукции строк в виде матрицы приведены на рис. 1.9, где дополнительный вектор - столбец содержит вычитаемые при редукции константы.

Рисунок 1.9 - Редуцированная по строкам матрица расстояний на 2 - м шаге алгоритма

Затем выполняем редукцию столбцов, результаты которой в виде матрицы приведены на рис. 1.10, где дополнительный вектор - строка содержит вычитаемые при редукции константы. Значение элемента, расположенного на пересечении вектора - столбца и вектора - строки , равно сумме всех вычитаемых констант: = 49. Это значение позволяет определить новую нижнюю границу длин всех маршрутов на данном шаге: = 298.

Дерево решений теперь может быть изображено так, как это показано на рис. 1.10.

Рисунок 1.10 - Редуцированная матрица расстояний на 2 - м шаге алгоритма

Рисунок 1.11 - Дерево решений на 2-м шаге алгоритма

По редуцированной матрице расстояний далее определяем минимальные ненулевые значения ее строк и столбцов, которые записываем соответственно в виде вектора - столбца и вектора - строки . Матрица вместе с этими векторами показана на рис. 1.12.

Рисунок 1.12 - Редуцированная матрица и значения минимальных ненулевых элементов для 2-го шага алгоритма

Соответствующие элементам векторов и значения вторичных штрафов для различных звеньев или пар вершин с нулевыми значениями расстояний между ними приведены в табл. 1.2.

Таблица 1.2 - Вторичные штрафы на 2 - м шаге алгоритма

←предыдущая  следующая→
1 2 



Copyright © 2005—2007 «Mark5»