Лекции 9-10. Расчет кратчайших маршрутов (1153086)
Текст из файла
ЛЕКЦИИ 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 заносится в формируемую строку маршрута, т.е.
→ ,завершается процедура и выводится список индексов узлов,составляющих маршрут .̂ маршрута :Пример определения по матрице 1bcan1bcccabn1) На шаге 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 < < ∞, если ≠ и = 10={}∞, если ≠ и = 0(6.8)Матрица 0 прямых маршрутов формируется по соотношению:, если = 10 = {}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 получаем кратчайшие маршруты ̂ .С̂ и 1C°, D°2C T i=0D T j=03i+14j+1нет5даi=j6j=n10k=jданет7k=08k+19нетk=iданетда11 k=nда12 Cktttij =C ik+C kj<C ijнетданет13C ij =C14D ij =ktkijt15 k=nданет16 j=nданет17i=nда<18C=C +19DR = DTРис. 6.3 Алгоритм определения кратчайших маршрутовнет6.3 Пример определения кратчайших маршрутовЗадана сеть, представленная на рис.
6.4. Требуется определить кратчайшиемаршруты, используя вычислительный алгоритм определения кратчайшихмаршрутов.Для формирования матрицы S конфигурации, (см. рис.6.5), используетсясоотношение (6.7).S=Рис. 6.4 Конфигурациязаданной сетиРис .6.5 Матрица SконфигурацииВ соответствии с п.1 алгоритма по соотношению (6.8) формируетсяматрица 0 взвешенных расстояний (см.
рис.6.6), и по соотношению (6.9)формируется матрица 0 прямых маршрутов, приведенная на рис. 6.7.00Рис. 6.6 Матрица 0Рис .6.7 Матрица 0Выполнение п.п. 3 – 11 алгоритма позволяет выбрать номера узлов i, j, k ,которые соответствуют ограничениям (6.4), (6.5).i=1, j=2, k=3По п.12 алгоритма вычисляются по соотношению (6.6)312= 13 + 32 = 11+∞ = ∞ и 12 = 103Так как 12> 12 , то повторяются п.п. 3 – 11 алгоритма и на одном из шаговвыбираются номера узлов i, j, k , которые соответствуют ограничениям (6.4),(6.5): i=1, j=4, k=2.214= 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.
В каком случае элемент матрицы = ∞ ?006. Поясните, что означает записи: 45= 0; 43= 3.Контрольные задания1. Рассчитайте кратчайшие маршруты, если в матрице 0 внесены следующиеизменения: 15 = 14; 51 = 14; 35 = ∞ 53 = ∞ .2. Сравните результаты, приведенные в примере 6.1 и полученные при расчетес внесенными изменениями3. Приведите запись кратчайших маршрутов: 15 и 51 для приведенного ирассчитанного вариантов..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
