| |
Контрольная: Основы построения телекоммуникационных систем 
Структура такой сети представлена на рис. 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 - м шаге алгоритма
Как видно из табл. 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, 3, 4
|
|
|
