Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 16
Текст из файла (страница 16)
Пусть А, В и С вЂ” векторы из множества 81К), т. е. А= [а„а~,..., ак), а, < а, <...< а„, а,.ЕР, В = [Ьг, Ьа,..., Ьк[, Ь < Ьа < ... ' Ь , Ь|ЕВ С= [см см. ° ° ~ ск[~ сг ( са ( ° . ( с|, с|~)Ь~ Пусть Тв — множество всех различных компонент векторов А и В. Обобщенная операция минимизации Ю определяется соотношением АЮВ=С, где с;=гп!и [Т+[, 1=1, ..., К.
Обобщенная операция сложения. Пусть А, В н С вЂ” векторы из множества $(К). Пусть ҄— множество всевозможных попарных сумм компонент векторов А и В. Обобщенная операция сложения Э определяется соотношением АЭВ=С, где с|=ш)п|[Тх! 1=1,-. К. Описание алгоритма. Выберем из множества 8(К) векторы Е=,[0, сс, сс, „,, сс1 н Ч= [со, сс,, сс|, Тогда для любого вектора Аеи8(К) справедливы следующие соотношения: АЪЧ = А, АЗЧ = Ч, А|3 Г = А. (2.55), (2.56), (2.57) Алгоритм двойного поиска, разработанный в [47), может быть описан следующим образом. Пусть узлы сети занумерованы от 1 до и, а длина каждой дуги (Ь 1) .равна |Ь|.
Введем обозначения Рм — — [|[н, ос, оо,..., ос) Ф(К), Р= [Р,.|), Ь=[Ьн[, где Ьц — Рм при |) 1; Ь,|=Ч при |< 1, 1)=[Вц), где 1)||=Рм при |(1, 1)п — — Ч при !)1. Здесь Рп, Ь|| н 1);; — векторы из 8(К), а Р, Ь и 1) — матрицы, элементами которых являются векторы нз 8(К). Если Детеряинироеаннме яотояи е сетях вт ,рассматриваемая сеть содержит более одной дуги, соединяющей узлы 1 и 1, то определим Рп как Рм=(УР, с(ем,...,с('тдоо,оо,..., ж) ~8(К), где с1'и, с(тп, ..., т1тп — длины дуг, соединяющих узлы 1 и 1. Отметим, что если 1)К, то вектор Рц не содержит бесконечных компонент.
Пусть Ее сии(К) — вектор, компонентами которого являются начальные оценки длин К кратчайших путей из источника в узел и. Предполагается„что если тп — источник, то первая компонента вектора Ее равна нулю. Определим массив Е(0) векторов Ес, (тп=1, 2, ..., п): Е(0) = [Ем, Ееь ..., Еся]. Отметим, что Е(0) также является вектором, компоненты которого суть элементы множества 8(К).
На тэ-и шаге алгоритма двойного поиска строится вектор Е(ш)=[Е ь Е ь..., Е,1, где Е элемент множества Ь('К), содержащий текущие оценки длин К кратчайших путей нз источника в узел гп. Построение векторов оценок выполняется с помощью следующих рекуррентных соотношений: Е(2г+1) = Е(2г)чтЕ(2г+1)®1, (2.58) Е (2г+ 2) = Е (2г+1)ЮЕ (2г+ 2)ЯЛУ. (2.59) Данные операции выполняются поочередно для каждого г= О, 1, 2,.... Если на некотором шаге в результате последовательного выполнения операций (2.58) и (2.59) будут получены одинаковые векторы оценок, то найденное, решение будет оптимальным.
Операции, определяемые соотношениями (2.58), (2.59), называются операциями обратного и прямого поиска соответственно. В каждом из этих соотношений в первую очередь выполняется обобщенная операция сложения. После того как будут найдены длины путей, выполняется процедура трассировки, позволяющая определить соответствующие пути. Остановимся на описании процедуры трассировки.
Предположим, что требуется найти гп-й кратчайший путь из источника в узел й Пусть Неи — длина этого пути и пусть узел 1 соединен дугой с узлом 1, Тогда Н, =Нм+с4, (2.60) где, как и раньше, с(п — длина дуги (1, 1), а Нп (1(еп) — длина 1-го кратчайшего пути нз источника в узел 1. Для каждого узла 1 процедура трассировки заключается в поиске узла 1, для которого выполняется соотношение (2.60). Как только узел 1 будет найден, мы вновь обращаемся к данной процедуре и выполняем ее до тех пор, пока не достигнем источника. Если требуется найти кратчайшие пути, не содержащие циклов, то описанную выше процедуру следует модифициро- 88 Глава 2 вать По сузцеству модифицированне заключается в следующем: если некоторый узел является «кандидатом» в узлы, принадлежащие рассматриваемому пути, то следует проверить, не был л" данный узел ранее получен с помощью соотношения (2.60).
282 П~ИМЕНЕНИЕ ЛЛГОРИтМЛ двОИНОгО поиснл Д РЕШЕНию модельнои злдлчи рассмотрим сеть, изображенную на рнс. 2.22. Для данной сети требуется найти длины трех кратчайших путей из узла 1 во все остальные узлы. 5 Источник Рис. 2.22. Сеть для модельного примера. Пзз ~зз ~14 ээээ Пзэ Оээ ээзг аз! 1эзэ ээээ ээээ ээээ з! ~2! 1У = (Озз) = э»э ! Р„! Ч '1г э' 'Р эГ 1», эг зг эзэа эвэз Вз! Вэ! данном примере К 3, п=4. В качестве произвольных допустимых векторов начальных оценок выберем векторы Ее!= = ей 21 221* Еоэ=Ееэ=Еоэ= '120, 21, 221.
Если выбор конечных он~ноя затруднен или невозможен, то все компоненты векторов можно положить равными со. Исключение составляет лишь оценка длины кратчайшего пути в источник, которая всегда полагается равной нулю. Матрица расстоянвй еэ, а также матрицы Е и 11 содержат по 16 элементов, каждый из которых является вектором иа множества 8(3).
Данные матрицы имеют следующий внд: 89 детерминированные иотони в сетях ч в, в„в, ч ч В„вхе Ч Ч вте ч ч ч ч ю=(во) = Для каждою вектора Рн одна из его компонент равна с(п, а К вЂ” 1=2 компоненты равны оо. Массив (АД вычисляется непосредственно из сети: 0 2 5 16 оо 0 2 3 с 2 0 10 5 со оо 0 Матрицы Р, Е и Ц задаются следующим образом: ее ь В качестве примера рассмотрим случай г О. В результате выполнения операции обратного поиска образуется вектор оценок Е (1) = Е (0)ЮЕ (1) ®Ье. Обобщенная сумма Е(!) 81 равна После выполнения операции обратного поиска получаем, что Е(1) =Е(0). Остановимся более подробно на вычислении век- 90 г г 00 - Е(1)(Х) 1.
о о 1 Е(0) Е(1) о 20 20 20 21 21 21 21 22 22 22 22 25 22 26 23 21 24 ] 2 Е(1) Рис. 2.23. Выполнение процедуры обратного поиска в модельном примере. ляются не элементы множества Й, а К-мерные векторы из 31К). Кроме того, вместо обычных операций + и )( выполняются операции Ю и Э соответственно. После того как вычислен некоторый столбец матрицы Е(1) 91., при помощи обобщенной операции минимизации производится его сравнение с соответствующим элементом вектора Е(0), в результате чего определяется соответствующий элемент вектора Е(1). На рис.
2.23 выписаны массивы Е(0), 1., Е(1)ЗЬ и показано, как с тора Е(1). Выполнение обобщенной операции сложения аналогично умножению справа вектора на матрицу с той лишь разницей, что элементы произведения вычисляются в обратном направлении. Однако в данном случае элементами массивов яв- Детермини ванные лотокы в сетях з 1О о г 21 20 5 14 22 21 20 15 г 21 24 Е (2) го г1 22 Е(2 5 го 14 !5 модельном примере. поиска в Наикратчайший путь 2.й кратчайший путь З.й кратчайший путь Рис. 2,25. Пути в модельном примере.
Рве, 2.24. Выполнение процедуры прямого 4 5 гг 20 21 22 4 14~ Е (2) (к) Ц' 15 О+ 21 20 Е (1) Глава л помощью процедуры обратного поиска вычисляются элементы вектора Е(1) '1. Затем выполняется первый шаг процедуры прямого поиска.
Данная операция записывается в виде Е(2) = Е(1) Ю Е(2) 8 1з. Обобщенная сумма Е(2)З() является следующим вектором, компоненты которого принадлежат множеству $(3): оо 2 4 5 оо 23 5 14 оо 24 22 15 Новый вектор оценок, Е(2), задается теперь матрицей 0 2 4 5 21 20 5 14 22 21 20 15 Далее, используя вектор Е(2)Э(), выполняем последовательность процедур, аналогичных тем, которые были описаны при вычислении обобщенной суммы Е(1)ЗЬ. При этом вычисления элементов производятся в прямом направлении, как показано на,рис. 2.24.
Продолжая аналогичные вычисления, мы получим результаты, приведенные в табл. 2.10. При г=2 в результате выполнения процедур обратного и прямого поиска мы получаем одно и то же решение. Как отмечалось выше, это означает, что данное решение является оптимальным.
С помощью процедуры трассировки, описанной рекуррентным соотношением (2.60), находятся наикратчайший и второй и третий кратчайшие пути из узла 1 в узел 4 (рис. 2.26). Отметим, что второй кратчайший путь содержит цикл. 2.6.3. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ АЛГОРИТМ ДВОЙНОГО ПОИСКА Назначение: определение длины кратчайшего пути из начального узла во все остальные узлы сети.
Локализация: подпрограмма КБНОгсТ в пакете сетевой оптимизации. о При вычислении Е(1) по формуле (*) вначале определяется вектор Езв Это возможно в силу того, что и-й столбец матрицы Ь состоит из векторов, все компоненты которого равны со. Далее по соотношению (з) определяется вектор Ем, м. Это возможно в силу того, что (и — 1)-й столбец матрицы Ь состоит из векторов, среди которых только у последнего могут быть компоненты, ие равные оо, и поэтому для вычисления Езы-и необходим только вектор Ез,.
Далее по соотношению (з) определяются векторы Еп -зь Еыз-зь ..., Егз,— Прим. перев. Детерминированные потоки е еетпе Таблица 2.10. Результаты работы алгоритма двойного поиска для модельной задачи Ограничения: программа обрабатывает сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме КЯНОКТ и в основной программе. Одновременно могут решаться одна или несколько задач. Входные данные: Набор 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
