2020-05-21
180
Заданы: места расположения центров коммутации и матрица расстояний [R].
Требуется определить: оптимальную двух кольцевую структуру сети (рис2) по критерию 
, где m=число ребер Гамильтонова цикла, структуры и размещения одного ребра образующее ее двух кольцевую суть.
Оценить: структурную живучесть сети в виде минимального суммарного числа возможных маршрутов между двумя произвольными центрами коммутации.
Критерий оптимальности: 
+Lkj 
| Рис.36. Проект «двух кольцевой» структуры сети. |
На рисунке 36 представлен макет «двух» топологической структуры с минимальной суммарной длиной кабеля Hmin = 95 у.е.
Следует отметить, что «двух кольцевая» структура всегда будет иметь большую суммарную длину кабеля, чем «одно кольцевая».
Алгоритм расчета «двух кольцевой» топологической структуры.
| Рис.37. Алгоритм расчета «двух кольцевой» топологической структуры |
Алгоритм решения включает:
1. Разложение исходной сети на две подсети.
2. В первой подсети с помощью алгоритма «Коммивояжер» определяется минимальное значение Гамильтонова цикла (
=min).
3. Длина ребра делящего сеть на две подсети определяется путем перебора ребра разделяющего сеть на подсети с заданным числом узлов. Если n – четное, то число переборов равно n/2,, если n – нечетное, то число переборов равно (n-1)+4, где n – число узлов сети.
4. Минимальное значение суммы всех длин ребер сети, будет равно ( + Lkj=min).
3.3 «Трех кольцевая» топологическая структура
Заданы: места расположения центров коммутации (абонентов) рис 1.; измерены расстояния между центрами и составлена матрица расстояний [R](см. задачу №1).
Требуется определить: оптимальную трех кольцевую структуру сети (рис3) по критерию 
где j-число ребер данной структуры сети.
Оценить: структурную живучесть сети в виде минимального числа возможных маршрутов между двумя любыми узлами (центрами коммутации сети).
Критерий оптимальности:[Г(s) + Lsj +Lsk + Lsm +Lkm]= min
| Рис.38. «трех кольцевая» структура сети. |
На рисунке 38 представлен макет «трех кольцевой» топологической структуры с минимальной суммарной длиной кабеля Hmin = 112 у.е.
Следует отметить, что «трех кольцевая» структура всегда будет иметь большую суммарную длину кабеля, чем «двух кольцевая».
Алгоритм расчета «трех кольцевой» топологической структуры. 
| Рис.39. Алгоритм расчета «трех кольцевой» топологической структуры. |
Алгоритм решения включает:
1. Разложение исходной сети на две подсети. Условием разложения является включение I-го узла исходной сети (i=1,n) во вторую подсеть. При этом задача «Коммивояжер» решается с меньшим числом узлов (узел I отсутствует).
2. Для сети, не содержащей узел решается задача «Коммивояжер». Находится минимальный Гамильтонов цикл.
3. Во второй подсети определяется суммарная длина четырех ребер [Lsj +Lsk + Lsm +Lkm]= min.
4. Минимальное решение находится переборным методом. Если I изменяется от 1 до N и n2 переборов для определения минимального значения суммарной длины ребер второй подсети.
Общее минимальное решение определяется, когда выполняется условие [Г(s) + Lsj +Lsk + Lsm +Lkm]= min
