←предыдущая следующая→
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
|
|