Контрольная: Основы построения телекоммуникационных систем 
Как видно из табл. 1.4, максимальное значение 
равно  . Выбирая
звено , можно
получить выигрыш в расстоянии, равный 
, т, е. больший, чем при выборе любого другого звена, за исключением звена
. В качестве базового звена на 4 - м шаге ветвления выбирается звено
, а  , 
Нижней границей длин маршрутов из подмножества 
на следующем (5 - м шаге) является величина 
= .
В модифицированной матрице 
расстояний после вычеркивания 3 -й строки и 1 -го столбца остается один нулевой
элемент, соответствующий звену 
(рис. 1.23).
Рисунок 1.23 - Текущая матрица расстояний для 5-го шага алгоритма
5 - й шаг. Поскольку в текущей матрице 
расстояний имеется только один нулевой элемент, соответствующий звену 
, то это звено является последним в определяемом маршруте длиной 
=300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.24.
Рисунок 1.24 -Дерево решений на 5-м шаге алгоритма
Построенный полный маршрут является оптимальным, если его длина не превосходит
длины любого маршрута, соответствующего другим звеньям дерева, что и имеет
место в данном примере. Он состоит из следующих звеньев или пар вершин 
и имеет суммарную длину 
=300. Этот оптимальный маршрут является минимальным гамильтоновым циклом,
который изображен на рис. 1.25.
Рисунок 1.25 - Минимальный гамильтонов цикл графа 
2 ОПРЕДЕЛЕНИЕ МНОЖЕСТВА ПУТЕЙ МЕТОДОМ ПОСТРОЕНИЯ ДЕРЕВА
Для графа (см. рис. 2.1) построим дерево путей из вершины 1. Данная вершина
является корнем дерева и размещается на нулевом ярусе. Значение ранга пути
здесь R = 0. На первом ярусе (R = 1) размещаются вершины 2, 3,
4, 5. которые имеют непосредственную связь с вершиной 1. Далее на втором ярусе
от вершины 2 размещаются вершины, которые связаны с вершиной 2, а именно 4 и 5.
Вершина 1 исключается из рассмотрения, поскольку путь в вершину 2 прошел через
вершину 1. От вершины 3 на втором ярусе записываются вершины 4 и 5, от вершины
4 — вершины 2, 3 и 5. А от вершины 5 – 2, 3, 4. Аналогично записываются вершины
на остальных ярусах дерева.
Построенное дерево для вершины-истока 1 представлено на рис. 2.2.
Как видим, в дереве есть четыре пути первого ранга (R = 1): a, e, g,
h; десять путей второго ранга (R = 2): ab, 
, ed,  , 
, gj, gc,  , 
, hf. на третьем ярусе (R = 3) записаны пути третьего ранга: abc,
abj,  , 
,  , edf, 
,  , 
, gjd,  , gcf, 
,  , 
, hfb. В конце концов, пути четвертого ранга (R = 4): 
, abjd,  , 
,  , 
, gjdf,  , hfbj.
Естественно, из дерева можно получить множество путей из фиксированной
вершины в любую вершину графа последовательным просмотром ярусов дерева. Так,
 =a+ +edf+ + + +gjdf+gcf+ + +hf;
 = +abj+ + +e+ +gj+ + + +hfbj;
 =ab+ + + +g+ + +hfb;
 =abjd+ +ed+ + +gjd+gc+h;
Рисунок 2.1 – Граф сети
Рисунок 2.2 - Дерево путей из вершины истока 1.
3 АНАЛИЗ СТРУКТУРНОЙ НАДЕЖНОСТИ СЕТИ ЭЛЕКТРОСВЯЗИ
Рассчитаем надежность связи между первой и всеми другими вершинами графа (1-2,
1-3, 1-4, 1-5). Будем считать заданный нами параметр р=0,817 равным для
всех ребер графа показанном на рис. 3.1. Тогда получаем:
Из результатов видно, что самая большая надежность у пути (1,4) равная 0,972.
Рисунок 3.1 – Надежность связи
Страницы: 1, 2, 3, 4
|
|
