Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 13
Текст из файла (страница 13)
Каждый элемент й1е1-1 (АФТИ) матрицы расстояний (начиная с первого элемента, т. е. расположенного в левом верхнем углу матрицы), который не принадлежит ни базовой строке, нн базовому столбцу, сравнить с суммой элементов йм1 ' и йп1 ' базовой строки и базового столбца соответственно. Если выполняется неравенство йп1 1+й1е1 1)с(;я1 ', то выбрать новые значения для 1 и й, перейти к следующему элен — 1654 Если трехместную операцию, определенную выражением (2.53), выполнять с данной парой узлов ( и й и всеми узлами ((Ф)чь1с) в порядке возрастания номеров 1', то значение ае;я, полученное на последней итерации, будет равно длине кратчайшей цепи из узла ( в узел й.
Мы воспользуемся матричным методом, который позволит нам запоминать длины кратчайших цепей и вх дуги. На каждой итерации алгоритма строятся две матрицы. Первая из них, называемая матрицей длин кратчайших путей,,содержит текущие оценки длин кратчайших цепей, т.
е. на 1'-й итерации данная матрица определяется как 01=~(с(1си]. Алгоритм начинает работу при 0'=,(Ы~;н), где ао;н=с;н. Затем, выполняя трехместную операцию (2.53) со всеми элементами матрицы Р', получаем 0' и т. д. до тех пор, пока для каждой пары узлов не будет выполнен критерий оптимальности (2.52). Вторая матрица, называемая матрицей маршрутов, служит для нахождения промежуточных узлов (если таковые имеются) кратчайших цепей. На 1-й итерации она определяется как Й1=(г11я), где т1м — первый промежуточный узел кратчайшей цепи из 11 в й, выбираемый среди узлов множества (1,2,...,1) (1Ф1ФЦ. Алгоритм начинает работу при Р= [то;е1, где Гаы=й.
На 1-й ИтЕрацИИ УЗЕЛ т1ея МОжЕт бЫтЬ ПОЛУЧЕН ИЗ СЛЕ- дующего соотношения. ( 1, если йгн1-') й111-'+й 1-', г11н = ~ [ теь1 ' в противном случае. Г*ава х менту д;ь~' ' и снова выполнить шаг 2. Если Ав' '>Ау' '+, +Й;„1 — ', то элементу д;в~-' матрицы длин кратчайших путей присвоить значение в5ьз=4~1'-'+дм~ — ', а соответствующему элементу матрицы маршрутов — значение, равное /. После просмотра всех элементов вновь перейти к выполнению шага 1 при 1=/+1. Прн 1=п будут построены матрица расстояний и матрица маршрутов, представляющие решение задачи.
Согласно (2.53), при получении Р~ из Р1 ' трехместную операцию, позволяющую установить факт принадлежности ба- зового узла кратчайшей цепи, следует выволиять только с эле- ментами матрицы Р~ ', не принадлежащими ни базовой стро- ке, ни базовому столбцу. Отметим, что при исследовании каждого элемента Авг ' 15 )ФА) может быть использована процедура, похожая на симплекс-метод.
После того как выбран элемент 4хг-', замену производить не следует, если с5ь/-'=оо и одно из двух значе- ний ди/ ' илн д,в~ ' равно оо, Если Ав/ '~со и одно из двух зна- чений А;г ' или 4в~ ' превосходит Ав~ ', то замену также про- изводить не следует. Поэтому необходимо рассмотреть лишь случай, когда Ав~ 'Фоо и оба значения А;~ ' и д~ьг 'чьоо меньше Ав1 '. Таким образом, для выполнения каждой итерации необходимо руководствоваться следующими правилами, позво- ляющими упростить вычисления: 1. А~~-'=со, т.
е. 1-й элемент базового столбца равен оо. Из (2.53) следует, что в данном случае значение Авl должно оста- ваться равным Ав/ '. Поэтому трехместную операцию выпол- нять не нужно. 2. И~в~-'=со, т. е. 1ий элемент базовой строки равен оо. Из (2.53) следует, что в данном случае значение Ау должно оста- ваться равным сну-'. Поэтому трехместную операцию выпол- нять не нужно.
Рассматриваемый алгоритм может быть описан в виде по- следовательности двух шагов вычислений. Начальные значе- ния Рв и Кв для итеративного выполнения этих шагов определя- ются по формулам Рв= 1с в], Кв= '1Ц, а параметру 1 присваива- ется начальное значение, равное нулю. Данный параметр исполь- зуется для обозначения базового узла на каждой итерации.
Шаг 1. /=1+1. Определить узел 1 как базовый узел и вычерк- нуть базовую строку и базовый столбец матрицы Р~' — '. Вычерк- нуть также строки в столбцы матрицы Р~' ', содержащие те элементы, равные оо, которые принадлежат базовой строке или базовому столбцу. Шаг 2. Сравнить каждый невычеркнутый элемент Авг ' с сум- мой следующих двух элементов: а) элемент А;~'-', расположенный на пересечении базового столбца и строки, содержащей Ав~-', 67 Детерминированные натеки в сете» б) элемент е1~е~ ',,расположенный на пересечении базовой строки и столбца, содержащего е1;е' '. Если сумма этих двух элементов меньше ейе~-', то положить 41;ег=Ау1-'+411е~ — ', т;е1=1. В противном случае положить Ае1=4е~-', т;ее=тле/-'.
После того как бУдУт, РассмотРены все невычеркнутые элементы матрицы 0'-', проверить выполнение условия 1=я. Если оно выполнено, то уабота алгоритма завершается, в противном случае перейти к шагу 1. 2.4.1. ПРИМЕР ЗАДАЧИ О МНОГОПОЛЮСНОИ КРАТЧАИШЕИ ЦЕПИ Для иллюстрации работы алгоритма Флойда найдем кратчайшую цепь между всеми парами узлов сети, изображенной на рис. 2.15. Начальные значения элементов матрицы длин кратчайших путей и матрицы маршрутов могут быть выбраны так, как это показано ниже. Поскольку п=оо, число итераций в алгоритме также равно 8.
7 8 4 5 б 3 оо со 1 2 3 0 9 со 6 оо 5 со 9 О оо 2 3 оо оо 7 7 со 4 8 7 оо 0 оо 10 0 4 34е 5 1 2 3 4 33о .5 6 7 8 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 0 2 2 0 со 4 оо 0 10 8 10 0 6 5 о 7 со о 9 12 4 5 б 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 б 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 б 7 8 Глава 2 Итерация 1. Узел 1=1 определяется как базовый. Следовательно, в матрице 1)о можно вычеркнуть первую строку и первый столбец. Кроме того, столбцы 3, б, 6, 7 и 8 содержат элементы, равные со и принадлежащие базовой строке, а строки 3, 6, Рис, 2.!8. Сеть в задаче о миогополюсной кратчайшей цепи.
1 2 3 4 5 б 7 8 Базовая строка Базовый столбец Рис. 2.16. Элементы, исследуемые (с помо|цью трехместной операции) на первой итерации. 6, 7 и 8 содержат элементы, равные оо и принадлежащие базовому столбцу. Поэтому, для того чтобы определить, приведет лн использование узла ! к более коротким цепям, следует исследовать (с помощью трехместной операции) лишь элементы матрицы Ро, изображенные на рис.
2.16. Поскольку диагональные элементы матрицы 0о можно не РассматРивать, необходимо исследовать лишь оценки г]оз„н г1олз. Применение трехместной операции дает следующие результаты: г]'ы = пип [г]а ~; г]ем+ г]вы] = ппп [оо; 9+ 3] = 12, гзаз = ппп [г]еаз', аиаз+г]ахв] = пип [оо; 3+9] = 12, Детерминироеаннае потоки е сетях Отметим, что оценки И'те=12 н с1'ее=12 лучше оценок е1озе =оо н ~Рея=ос соответственно. Поскольку использование базового узла приводит к более коротким цепям из узла 2 в узел 4 и из узла 4 в узел 2, то полагаем т'з4= 1 н т',з=1. Все остальные элементы матриц Ро и йо остаются без изменения.
Теперь мы можем выписать матрицы Р' и й'т 1 2 3 4 О 9 оо 3 9 0 2 12 со 2 0 2 3 12 2 0 оо 7 4 со со со 8 оо со оо 6 5 5 6 7 8 7 о со оо 4 8 б оо со 5 0 10 оо 10 0 7 оо 7 0 9 12 10 Э' = 4 5 1 2 3 4 5 1 2 3'4'5 1 2,3 1 5 1 2 3 4 5 1 1 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1'2 3 4 5 б 7 8 Итерация 2. Определяем узел 1=2 как базовый и вычеркиваем в матрице Ва вторую строку и второй столбец.
Кроме того, столбцы 6, 7 и 8 содержат элементы, равные оо и принадлежащие базовой строке, а строки 6, 7 и 8 содержат элементы, равные оо и принадлежащие базовому столбцу. Поэтому, для того чтобы определить, приведет ли использование узла 2 к более коротким цепям, следует исследовать (с помощью трехместной операции) лишь элементы матрицы 13', изображенные на рнс. 2.17. Поскольку диагональные элементы матрицы Р' можно не рассматривать, то необходимо исследовать элементы И'1з, е1'ы, срж.
о'зь зз~з4, о~зз, и~4ь ез'ез, и~ее, зз~зь Узз и о'зь Нетрудно про- 1 2 3 4 йт = 5 6 б 7 8 6 7 8 б 7 8 б 7 8 6 7 8 6 7 8 б 7 8 6 7 8 70 Г««аеа 3 верить, что улучшены могут быть только оценки «з«11, «Рм, «Рзь «!144, «5'41 и «5144. Новые оценки получаются следующим образом з «]114+ «Рзз] = пип [оо; «Рзз+«[141] = пйп [оо; «Р,+«Р, ] = пип [оо; «Рзз+«Р ] пип [оо «Р, +«Рз ] = пйп [оо; «Р,з+«[144] = пип [оо; Таким образом, гз«з=гз«зе хзз«=гзббе хзб«=г'б«=2 и гз«4= г««з для всех влементов, таких, что «Р«з=«Р«ь Новые матрицы ]34 и [бз имеют вид 2 3 9 11 0 2 2 0 12 2 7 4 оо 8 б 4 5 6 7 3 16 б 12 7 оо аа 2 4 8 6 0 19 о 5 19 0 10 « оо 10 0 7 5 об 7 0 об 9 12 !О 111 = 4 5 б 7 8 О 3 4 5 2 4 2 3 1 5 3 4 5 3 4 2 3 2 5 3 4 5 3 4 5 3 4 5 1 2 1 2 1 2 г .г 1 1 2 2 1 2 1 2 1 2 4 Из = 5 Выполняя аналогичные вычисления на итерациях 3, 4, 6, 6, 7, 8, мы получим результаты, приведенные в табл.
2.6. Нетрудно проверить, что оценки, полученные на итерациях 6, 7 и 8, не могут быть улучшены. Следовательно, оптимальное реше- й'„= пнп [«[114; «Рзб = шш [«Рзб «Рзз пип [«11зз; «Р4б шнз [«" 41! «Р,з пйп [«Реб «Рзб пип [«[1 4 0 9 1! 3 !б 6 7 8 6 7 8 6 7 8 6 7 8 б 7 8 6 7 8 б 7 8 6 7 8 6 7 8 9+2]=11, 9+7] = 16, 2+9] = 11, 12+7] = 19, 7+9]=16, 7+12] = 19. 71 Детерминированные потоки в сетях Таблица З.б. Результаты вычислений для модельного примера ИтеРация 15 !9 !7 б 10 8 11 3 2 4 0 2 2 0 4 6 8 10 б 5 0 9 9 0 11 2 3 4 15 б 19 10 Ы 8 0 7 5 3 7 0 2 4 5 2 0 2 4 2 О 9 б 4 б 13 10 8 10 8 3 б 5 О 7 5 3 7 0 2 4 5 2 0 2 3 4 2 0 9 б 4 б !3 10 8 10 8 8 б 5 !3 !5 13 15 Остаатся Остаатся Остается неизменной неизменной неизменноа ние соответствует матрицам Р' и Кз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
