Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
ЛЕКЦИИ 9-10
РАСЧЕТ КРАТЧАЙШИХ МАРШРУТОВ
6.1 Постановка задачи
Для вычислительных сетей актуальной задачей является выбор кратчайших
маршрутов. Успешное решение этой задачи позволяет:
- повысить производительность вычислительной сети,
- повысить эффективность использования ресурсов,
- сократить время реакции вычислительной сети при обслуживании
пользователей.
Рассматриваемая задача может быть сформулирована следующим образом.
Пусть задана конфигурация S, содержащая множество узлов 𝑎𝑖 ∈A, i = ̅̅̅̅̅
1, 𝑛,
пара которых 𝑎𝑖 и 𝑎𝑗 может быть соединена дугой 𝑠𝑖𝑗 Узлы 𝑎𝑖 , 𝑎𝑗 соответствуют
устройствам ВС, а дуги 𝑠𝑖𝑗 – каналам, соединяющим устройства ВС. Узлы 𝑎𝑖
размешены во взвешенном пространстве М и каждой дуге 𝑠𝑖𝑗 соответствует
взвешенное расстояние 𝑐𝑖𝑗 . Соединение каждой пары узлов 𝑎𝑖 и 𝑎𝑗
обеспечивается маршрутом 𝜇𝑖𝑗 , который состоит из последовательно
соединенных дуг и однозначно определяется номерами узлов, т.е. 𝜇𝑖𝑗 = {i,…k,
j}.
Между узлом 𝑎𝑖 (источником) и узлом 𝑎𝑗 (целью) могут находиться
несколько
узлов, 𝑎𝑎 , 𝑎𝑏 , 𝑎𝑐, 𝑎𝑑
тогда
маршрут
𝜇𝑖𝑗 =
{i,a,b,c,d,j}
–
последовательность дуг, образующих связную цепь между узлами i и j.
Например, i-a, a-b, b-c, c-d ,d-j представляет собой маршрут 𝜇𝑖𝑗 ={i
→a→b→c→d→j}.
Требуется определить, при каком выборе последовательности {i,…k, j}
узлов в каждом маршруте 𝜇𝑖𝑗 обеспечивается минимальная суммарная длина 𝐶̂𝑖𝑗
взвешенных расстояний 𝑐𝑖𝑗 . дуг 𝑠𝑖𝑗 соответствующих конфигурации S и
включенных в маршрут 𝜇𝑖𝑗 .
Целевая функция сформулированной задачи.
𝐶̂𝑖𝑗 = min𝑢𝑡 ∑𝑢𝑡∈𝜇𝑖𝑗 𝐶𝑢𝑡 𝑥𝑢𝑡
(6.1)
где 𝑎𝑢 - начальный узел дуги 𝑠𝑢𝑡 ; 𝑎𝑡 – конечный узел дуги 𝑠𝑢𝑡
Рис. 6.1 Дуга 𝑠𝑢𝑡 , 𝑠𝑢𝑡
𝑥𝑢 - булевые неизвестные, удовлетворяющие соотношениям:
1, если 𝑢 ∈ 𝜇𝑖𝑗
𝑥𝑢 = {
(6.2)
}
0, если 𝑢 ∉ 𝜇𝑖𝑗
𝑦𝑡 - булевые неизвестные, удовлетворяющие соотношениям:
1, если 𝑡 ∈ 𝜇𝑖𝑗
𝑦𝑡 = {
}
0, если 𝑡 ∉ 𝜇𝑖𝑗
Ограничения: 𝑖 ≠ 𝑗 𝑢 ≠ 𝑡 𝑖 ≠ 𝑡
(6.3)
𝑢≠𝑗
𝑖 ≠ 𝑛 𝑗 ≠ 𝑛 (6.4)
6.2 Алгоритм определения кратчайших маршрутов
В основу излагаемого вычислительного алгоритма положены идеи
алгоритма на графах, который предложил Дейкстра.
В вычислительном алгоритме для поиска оптимального решения
используется процедура 1.
Рассмотрим три узла 𝑎𝑖 , 𝑎𝑗 , 𝑎𝑘 , соединенных дугами 𝑠𝑖𝑗 , 𝑠𝑖𝑘 , 𝑠𝑘𝑗 для
которых известны взвешенные расстояния 𝑐𝑖𝑗 , 𝑐𝑖𝑘 , 𝑐𝑘𝑗 , как показано на рис.6.2.
𝑠𝑖𝑘 , 𝑠𝑘𝑗 ,
k ≠i, k ≠ j , k≤n.
(6.5)
Рис.6.2. Процедура поиска
оптимального решения
Пусть необходимо найти кратчайший маршрут 𝜇̂ 𝑖𝑗 между узлами 𝑎𝑖 , 𝑎𝑗 . В
рассматриваемом случае между узлами 𝑎𝑖 , 𝑎𝑗 может быть два маршрута:
𝜇𝑖𝑗 – прямой, имеющий взвешенное расстояние 𝐶𝑖𝑗 = 𝑐𝑖𝑗 ;
𝑘
𝜇𝑖𝑗
– с промежуточным узлом, имеющий взвешенное расстояние;
𝐶𝑖𝑗𝑘 = 𝑐𝑖𝑘 + 𝑐𝑘𝑗 .
(6.6)
Для выбора оптимального маршрута применяются следующие правила:
𝑘
1) если 𝐶𝑖𝑗 >𝐶𝑖𝑗𝑘 , то выбирается маршрут 𝜇𝑖𝑗
={i,k,j} c промежуточным узлом;
𝑘
2) если 𝐶𝑖𝑗 ≤ 𝐶𝑖𝑗 , то выбирается прямой маршрут 𝜇𝑖𝑗 ={i,j}.
Для вычислительного алгоритма используются следующие формы
представления заданных, промежуточных и результирующих данных.
Конфигурация S задается матрицей ‖𝑠𝑖𝑗 ‖ , где 𝑠𝑖𝑗 = (0,1).
Взвешенные расстояния задаются матрицей 𝐶 0 =
отсутствующе в конфигурации (𝑠𝑖𝑗 = 0), имеют 𝑐𝑖𝑗 = ∞.
‖𝑐𝑖𝑗 ‖,
где
дуги,
Результаты расчетов представлены в виде матриц:
𝐶̂ =‖𝐶̂𝑖𝑗 ‖ – матрица взвешенных расстояний кратчайших маршрутов 𝜇𝑖𝑗 .
̂ =‖𝐷
̂𝑖𝑗 ‖ – матрица взвешенных расстояний кратчайших маршрутов 𝜇𝑖𝑗 , в
𝐷
которой на основании свойства вложенности размещается полный набор всех
𝑛2 кратчайших маршрутов 𝜇𝑖𝑗 (𝑖, 𝑗 = ̅̅̅̅̅
1, 𝑛).
̂𝑖𝑗 ‖ используется
Для определения 𝜇𝑖𝑗 по сформированной матрице ‖𝐷
пошаговая процедура 2.
Для шага g=1, (n-2>g≥1), индекс i заносится в формируемую строку
маршрута, т.е i→ 𝜇𝑖𝑗 .
̂𝑖𝑗 ≠ j ,то переход к пункту 3, если
Проверяется, если значение 𝐷
̂𝑖𝑗 = j ,то переход к пункту 4.
значение 𝐷
̂𝑖𝑗 (𝑔) заносится в формируемую строку маршрута, т.е.
Значение 𝐷
1)
2)
3)
̂𝑖𝑗 (𝑔) → 𝜇𝑖𝑗 , изменяется номер шага g= g+1 и переход к пункту 2.
𝐷
4) Значение j заносится в формируемую строку маршрута, т.е. 𝑗 → 𝜇𝑖𝑗 ,
завершается процедура и выводится список индексов узлов,
составляющих маршрут 𝜇𝑖𝑗 .
̂ маршрута 𝜇𝑎𝑐 :
Пример определения по матрице 𝐷
1
b
c
a
n
1
b
c
c
c
a
b
n
1) На шаге g=1, 𝜇𝑎𝑐 = {a}.
̂𝑎𝑐 (1) = b, b≠c переход к пункту 3.
2) 𝐷
3) , 𝜇𝑎𝑐 = {a,b}, g=2 переход к пункту 2.
̂𝑎𝑐 (2) = c, b=c переход к пункту 4.
2) 𝐷
4) Результат: 𝜇𝑎𝑐 = {a,b,c}.
Вычислительный
алгоритм
определения
кратчайших
маршрутов,
приведенный на рис.6.3, включает процедуры 1 и 2 и содержит следующие
пункты.
1. Для заданной сети с конфигурацией S=‖𝑠𝑖𝑗 ‖, формируются:
матрица ‖𝑠𝑖𝑗 ‖ конфигурации, матрица 𝐶 0 взвешенных расстояний и матрица
𝐷0 прямых маршрутов.
Матрица ‖𝑠𝑖𝑗 ‖ конфигурации формируется по соотношению:
1, если существует прямой канал от 𝑎𝑖 к 𝑎𝑗
1, если 𝑖 = 𝑗
𝑠𝑖𝑗 = {
} (6.7)
0, если не существует прямого канала от 𝑎𝑖 к 𝑎𝑗
Матрица 𝐶 0 взвешенных расстояний формируется по соотношению:
0, если 𝑖 = 𝑗
0 < 𝑐𝑖𝑗 < ∞, если 𝑖 ≠ 𝑗 и 𝑠𝑖𝑗 = 1
𝑐𝑖𝑗
={
}
∞, если 𝑖 ≠ 𝑗 и 𝑠𝑖𝑗 = 0
(6.8)
Матрица 𝐷0 прямых маршрутов формируется по соотношению:
𝑗, если 𝑠𝑖𝑗 = 1
𝐷𝑖𝑗0 = {
}
0, если 𝑠𝑖𝑗 = 0
(6.9)
2. Резервируются для текущих значений матрицы С𝑇 и 𝐷𝑇 , устанавливаются в
ноль счетчики индексов начальных (i) и конечных (j) узлов.
3, 4. Увеличиваются значения счетчиков индексов начальных (i) и конечных
(j) узлов.
5, 6. Проверяются ограничения
i ≠ j , j=n.
7. Устанавливается в ноль счетчик индексов промежуточных (k) узлов.
8. Увеличивается значение счетчик индексов промежуточных (k) узлов.
9,10,11. Проверяются ограничения k ≠i, k ≠ j , k=n.
12. В соответствии с процедурой 1 вычисляется текущее значение взвешенных
расстояний с𝑘𝑖𝑗 маршрута через промежуточный узел и сравнивается с
значением прямого маршрута. Если условие выполняется, то переходим к п. 13,
если не выполняется – к п.15.
расстояний 13, 14. Заносятся значения:
с𝑘𝑖𝑗 в текущую матрицу С𝑇
взвешенных и k – в текущую матрицу 𝐷𝑇 маршрутов.
15, 16,17. Проверяются ограничения k=n, j=n, i=n.
18,19. Текущие значения С𝑇 и 𝐷𝑇 записываются в результирующие матрицы
̂ . Используя процедуру 2 получаем кратчайшие маршруты 𝜇̂ 𝑖𝑗 .
С̂ и 𝐷
1
C°, D°
2
C T i=0
D T j=0
3
i+1
4
j+1
нет
5
да
i=j
6
j=n
10
k=j
да
нет
7
k=0
8
k+1
9
нет
k=i
да
нет
да
11 k=n
да
12 C
k
t
t
t
ij =C ik+C kj 𝑐12 , то повторяются п.п. 3 – 11 алгоритма и на одном из шагов
выбираются номера узлов i, j, k , которые соответствуют ограничениям (6.4),
(6.5): i=1, j=4, k=2.
2
𝐶14
= 𝑐12 + 𝑐24 = 10 + 12 = 22 и 𝑐14 = ∞
2
Так как 𝐶14
<𝑐12 , то переходим к п.13.
Т
2
По п.13 в матрице C T значению c14
присваивают C14
= 22.
Т
По п.14 в матрице DT значению d14
записывается k = 2.
Последовательное выполнение алгоритма заканчивается, если i =5, j =5, k =5 .
Результат расчета: матрица C T записывается в матрицу 𝐶̂ (см. рис.6.8), матрица
̂ (см. рис.6.9) .
DT записывается в матрицу 𝐷
𝐶𝑇
𝐷𝑇
𝐶̂ =
̂=
𝐷
Рис. 6.8 Матрица 𝐶 0
Рис .6.9 Матрица 𝐷0
Для определения кратчайшего маршрута между любыми заданными узлами
используется процедура 2.
Например, если i =2, j =5, , то 𝜇25 = (2,1,3,5).
Самоконтроль знаний
Контрольные вопросы
1. Сформулируйте вербальную постановку задачи, в которой выделите
исходные данные, ограничения и требуемый результат.
2. Чем отличается начальный узел дуги от конечного?
3. Может ли 𝑠𝑢𝑡 = 𝑠𝑡𝑢 и при каких условиях?
4. Каким способом на каждом шаге выбирается решение, обеспечивающее
выбор кратчайшего маршрута?
5. В каком случае элемент матрицы 𝑐𝑖𝑗 = ∞ ?
6. Поясните, что означает записи: 𝐷45
= 0; 𝐷43
= 3.
Контрольные задания
1. Рассчитайте кратчайшие маршруты, если в матрице 𝐶 0 внесены следующие
изменения: 𝑐15 = 14; 𝑐51 = 14; 𝑐35 = ∞ 𝑐53 = ∞ .
2. Сравните результаты, приведенные в примере 6.1 и полученные при расчете
с внесенными изменениями
3. Приведите запись кратчайших маршрутов: 𝜇15 и 𝜇51 для приведенного и
рассчитанного вариантов.