![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Компьютерные сети
|
16.01.2005
|
![]() |
![]() |
|||
3.7.Задача ВПС РП 3.7.1.Постановка задачи. Задано: структура сети при ограничении и условии, что 3.7.2.Алгоритм решения ВПС РП. Предложенный алгоритм А3 использует многократное решение комбинации задач ВПС РП. Он состоит из начального этапа и конечного числа однотипных итераций Начальный этап. 1. В качестве метрики 2. Определяем кратчайшие пути в сети с выбранной метрикой 3. Решаем задачу ВПС по критерию Переходим к 1-ой итерации. Пусть уже проведено k итераций и найден некоторый поток в сети (k+1)-а итерация. 1. Решаем задачу РП при заданных пропускных способностях 2. При новом распределении потоков 3. Вычисляем новое значение критерия 3.7.3.Алгоритм нахождения кратчайших путей и расчёта трафиков. В процессе работы алгоритмов ВПС РП и нахождения максимального потока в сети при отказах многократно используется алгоритм нахождения кратчайших путей и расчёта информационных потоков (трафиков) в многосвязной сети. Пусть имеем многосвязную коммуникационную сеть, которая задана в виде графа G(X,E),где Необходимо рассчитать параметры сети G(X,E): такие маршруты передачи информации и информационные потоки в каждом канале frs, Исходные данные: матрица смежности матрица удельных стоимостей передачи информации В процессе работы алгоритма используются такие рабочие матрицы:
Описание алгоритма. Алгоритм состоит из конечного числа однотипных итераций, в ходе которых строят и уточняют матрицы A(k),M(k). 1-я итерация. 1.Определяем матрицу 2.Заполняем матрицу маршрутов М(1),в соответствии с соотношением Таким образом в результате 1-ой итерации рассчитаны характеристики сети для маршрутов длины 1. 2-я итерация. Определяем минимальные маршруты длиной=2 и рассчитываем А(2),М(2). 1.Просматриваем i-тую строку матрицы А(1),i=1,2... и определяем
2.Если aij(1)=aij(2),то mij(2)=mij(1) и приравнивая j=j+1,переходим к рассмотрению следующего элемента i-той строки. Если mij(2)=msj(1) (3.31) 3.Меняем i от 1 до n и выполняем шаг 2 со всеми строками матрицы А(1). 4.Если А(2)=А(1) и М(2)=М(1) и в матрице нет пустых элементов, то конец работы алгоритма, иначе переходим к следующей итерации. Пусть проведено (k-1) итераций в ходе которых построены матрицы A(k-1),M(k-1). В ходе выполнения k-той итерации строим A(k),M(k), где M(k)-маршрутная матрица, которая содержит минимальные пути длиной не более 2(k-1) (по количеству каналов). 1.Просматриваем i-тую строку матрицы A(k-1) и определяем aij(k):
2.Если aij(k)=aij(k-1),то mij(k)=mij(k-1) приравнивая j=k+1 переходим к рассмотрению следующего элемента i-той строки. Если 3.Если A(k)=A(k-1) и M(k)=M(k-1) и в матрице M(k) нет пустых элементов, то конец работы алгоритма, матрица M(k)=M-матрица кратчайших путей, а A(k)=A-соответствующая ей матрица длин этих путей. Иначе переходим к k+1-й итерации. Итак, допустим, что построена маршрутная матрица М. Покажем, как при помощи её можно найти кратчайший путь 1.Рассмотрим элемент mij. Если mij=i, то конец 2.Находим в матрице М элемент 3.Если s2=i, то конец работы алгоритма, искомый путь Допустим, что через k итераций получен элемент Теперь можно рассчитать матрицу информационных потоков по кратчайшим путям. Алгоритм расчета потоков состоит из k=n(n-1) итераций. 1-я итерация. 1.Выбираем 1-й элемент h12 из матрицы Н. 2.Находим кратчайший путь 3.Тогда Пусть уже проведено (k-1) итераций и определён вектор F(k-1). k-тая итерация. 1.Из матрицы Н выбираем следующее требование, ещё не распределённое по сети. Пусть это 2.Определяем кратчайший маршрут 3.Пересчитываем величину суммарного трафика на каналах маршрута 4. Проверка условия k=n(n-1). Если да, то конец, иначе k=k+1 и переход на шаг 1 (k+1)-й итерации. Пример 1. Рассмотрим задачу нахождения кратчайших путей и потоков по кратчайшим путям для сети, приведенной на рис. 1. На дугах (i,j) сети указаны условные стоимости передачи Сij, причём Cij=Cji. Матрица требований в передаче информации Н приводится ниже. рис. 1. i\j 1 2 3 4 5 1 x 13 11 7 9 2 6 x 6 4 8 H= 3 5 4 x 6 3 4 6 14 12 x 15 5 1 6 7 3 x i\j 1 2 3 4 5 1 x 1 0 1 0 2 1 x 1 0 0 B= 3 0 1 x 1 1 4 1 0 1 x 1 5 0 0 1 1 x 1 итерация. Вычисляем матрицу длин кратчайших путей А(1): i\j 1 2 3 4 5 1 x 7 2 7 x 7 A(1)= 3 4 9 5 Находим матрицу кратчайших маршрутов
i\j 1 2 3 4 5 1 x 1 0 1 0 2 2 x 2 0 0 M(1)=3 0 3 x 3 3 4 4 0 4 x 4 5 0 0 5 5 x 2 итерация Вычисляем матрицу длин кратчайших путей длин 2 А(2): i\j 1 2 3 4 5 1 x 7 14 9 18 2 7 x 7 16 11 A(2)= 3 14 7 x 10 4 4 9 16 10 x 9 5 18 11 4 9 x Находим соответствующую матрицу кратчайших маршрутов. i\j 1 2 3 4 5 1 x 1 2 1 4 2 2 x 2 3 3 M(2)=3 2 3 x 3 3 4 4 3 4 x 4 5 4 3 5 5 x 3 итерация Вычисляем матрицу длин кратчайших путей А(3) и соответствующую маршрутную матрицу М(3) и убеждаемся, что А(3)=А(2) и М(3)=М(2). Следовательно, матрица М(2)=М является искомой маршрутной матрицей (кратчайших путей), а А(2)=А соответствующих длин кратчайших путей. Покажем, как пользуясь матрицей М, найти кратчайший путь Рассматриваем элемент m15=4. Далее ищем элемент m14, т.к. m14=1, то конец, Рассчитываем потоки по кратчайшим путям: 1 итерация Выбираем элемент h12=13. Находим k=k+1 и переход к следующей итерации. Остальные итерации выполняются аналогично. Спустя k=n(n-1)=20 итераций получим следующее распределение потоков по кратчайшим путям: |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |