| |
Контрольная: Основы построения телекоммуникационных систем 
Как видно из табл. 1.2, максимальное значение 
равно  . Выбирая
звено  , можно
получить выигрыш в расстоянии, равный 
, т, е. больший, чем при выборе любого другого звена, за исключением звена
,  , 
. Следовательно, в качестве базового звена на 2 - м шаге ветвления выбирается
звено , а 
,  Нижней границей
длин маршрутов из подмножества 
на следующем (3 - м шаге) является величина 
= .
Модифицированная матрица 
расстояний после вычеркивания 1 -й строки и 2 -го столбца имеет вид, приведенный
на рис. 1.13.
Рисунок 1.13 - Текущая матрица расстояний для 3-го шага алгоритма
3 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.14, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.14 - Редуцированная по строкам матрица расстояний на 3 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.15, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 2. Это значение позволяет определить новую нижнюю границу 
длин всех маршрутов на данном шаге: 
= 300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.16.
Рисунок 1.15 - Редуцированная матрица расстояний на 3 - м шаге алгоритма
Рисунок 1.16 - Дерево решений на 3 - м шаге алгоритма
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.17.
Рисунок 1.17 - Редуцированная матрица и значения минимальных ненулевых
элементов для 3-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.3.
Таблица 1.3 - Вторичные штрафы на 3 - м шаге алгоритма
Как видно из табл. 1.3, максимальное значение 
равно  . Выбирая
звено  , можно
получить выигрыш в расстоянии, равный 
, т.е. больший, чем при выборе любого другого звена, за исключением звена 
,  , 
. Следовательно, в качестве базового звена на 3 - м шаге ветвления выбирается
звено , а 
,  Нижней границей
длин маршрутов из подмножества 
на следующем (4 - м шаге) является величина 
= .
Модифицированная матрица 
расстояний после вычеркивания 2-й строки и 4 -го столбца имеет вид, приведенный
на рис. 1.18.
Рисунок 1.18 - Текущая матрица расстояний для 4-го шага алгоритма
4 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.19, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.19 - Редуцированная по строкам матрица расстояний на 4 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.20, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 0. Это значение позволяет определить новую нижнюю границу 
длин всех маршрутов на данном шаге: 
= 300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.21.
Рисунок 1.20 - Редуцированная матрица расстояний на 4 - м шаге алгоритма
Рисунок 1.21 - Дерево решений на 4-м шаге алгоритма
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.22.
Рисунок 1.22 - Редуцированная матрица и значения минимальных ненулевых
элементов для 4-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.4.
Таблица 1.4 - Вторичные штрафы на 4 - м шаге алгоритма
Страницы: 1, 2, 3, 4
|
|
|
