Расчет кратчайших маршрутов

ЛЕКЦИИ 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 для приведенного и рассчитанного вариантов.