Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 33
Текст из файла (страница 33)
Алгоритм, рассматриваемый ниже, позволяет получить таков дерево. Итак, надо построить дерево, которое содержит кратчайшие цепи из узла № во все остальные узлы сети. Дуги сети, принадлен1ащие этому дереву, будем называть дугами дерева, а дуги, не принадлежащие ему — дугами ене дерева. После того как дерево будет построено, каждая кратчайшая цепь будет состоять из дуг' дерева. В начале алгоритма все дуги сети считаются дугами вне дерева.
В процессе работы алгоритма количество дуг дерева постепенно увеличивается от О до и — 1, где п — число узлов данной сети. Работа алгоритма начинается следующим образом: полагаем, что узел № принадлежит искомому дереву. Предполо1ким теперь, что найдено т дуг дерева (т = О, 1,..., п — 2).
Длину кратчайшей цепи из узла № в узел 1У» обозначим Ь,». Рассмотрим цепи из № в Х«'», содерн«ащие, кроме дуг дерева, не болев одной дуги вне дерева. Длину кратчайшей среди таких цепей обозначим Х,;». Если все цепи из № в 1У» содержат на некотором шаге алгоритма больше одной дуги вне дерева, то полагаем Х,;» — — сс. Заметим, что величина Х;» зависит от т: она изменяется по мере увеличения т. Вообще говоря, Х;» в Х,». Предположим, что в ходе алгоритма построена часть искомого дерева, которую будем называть текущим деревом.
Узел 1У» (не принадлежащий текущему дереву) будем называть соседним с этим дерееом, если в сети имеется дуга А1» или дуга Л»О где № — некоторый узел текущего дерева. Тогда цепь длины Х;1 из узла № в узел № дерева содержит только дуги дерева, и слодовательпо, Х,'1 = В,ь Из определения Х„'» следует, что Х,;» = вцг.(Х г1 + д 1») 1 где минимум берется по всем узлам текущего дерева. 11усть № — тот иэ соседних с текущим деревом узлов 1У», который обладает минимальной величиной Х.,» .
Х,„.= нип Х,;», в»ь кглтчлншвв пипи 193 а Х~ — тот из узлов Л'; дерева, на котором достигается зтот минимум: Х;„=шш(Хм+4,) =Х,т+Ы;„. Покажем, что тогда $ Хвг = Хвг~ а дуга Ахт должна принадлежать искомому дереву. Рассмотрим произвольную цепь из узла Л', в узел Х„, Так как узел Х, принадлежит текущему дереву, а узел Л', ему не принадлежит, то всегда мо»кно найти в рассматриваемой цепи первый узел Х», нс принадлежащий дереву (в частности, таким узлом Ф» может оказатъся сам узел Ж,). Из определения Гдследует, что любая цепь из Л', в Х„проходящая через узел Л», будет не короче, чем Х» (здесь используется предположение, что все расстояния Ы; эО; в противном случае участок цепи из Х» в Л', может оказаться отрицательным).
А так как Х;»)Х,;„то длина рассматриваемой цепи из Х, в Л', будет не короче, чем Х,„. Но цепь имеет длину, равную в.точности Х;„. Следовательно, Х в~ = Х м и дуга Аз должна быть включена в число дуг дерева. (Заметим, что на последующих шагах алгоритма величина Х;„ не может стать меньше, чем Х„.) На каждом шаге алгоритма число дуг дерева увеличивается па единицу, при етом величины Хл',» должны быть пересчитаны для всех узлов, соседних с вновь построенным деревом.
Для етого имеющаяся величина Х;» сравнивается с величиной Х„+д,». Если Х„+и» ( Ь,», то параметру Х,» присваивается значение Х,„+ +о„»; если же Х,„+А„»)Х,;», то Х» остается без изменения. Си»1волически зто записывается в следу»ощем виде: Х'» '=ш(п(Х'», Х" +йт») где символ: =обозначает оператор присвоения.
Теперь можно привести весь алгоритм решения задачи. Шаг О. Положить, что узел Л', принадлежит дереву; Х„=О; для соседних с Х, узлов Х,» =сЦ, для остальных Х»»= со. Шаг 1. Положить Х„= ш1п Х;»= Х,~+0,„, где Х» — все узлы, соседние с текущим деревом. Дугу А;„включить в число дуг дерева. Шаг 2, Если число дуг дерева равно и — 1, то конец. Если нот, перейти к шагу 3. Шаг 3. Х;» . '=ш1п(Х;», Х,„+й„»).
Перейти к шагу 1. Этот алгоритм мов'ет быть осуществлен при помощи расставовки пометок. Как дый узел Х» получает пометку вида (Х,, 1). Первая часть пометки — зто величина Х;» или Х,», а вторая часть указывает соседний с Л'» узел в кратчайшей цепи из Х, в Х». Пометка называется временной, если она имеет вид(Х,», |), и лостоян- 13 т. хт 494 ГЛ. !З. 1СРАТЧАИ!ВИГ ПЕПИ И !!ОТОКП ЫПНПЫАЛЬИОЙ СТОИЗ!ОСТИ исй, если она имеет вид (Ьвд, 1). Вначале казкдый узел Хд, соседний с узлом Дс„получает временпую пометку (с5,д, г) =(Ь;д, г). Коли Ьвв=шшЬ,А, то узел Х„получает постоянную пометку ь (Ьвв, з)=(Ь,„, г). Подсчитаем, какое число операций сложения и сравнения требуется для выполнения алгоритма. На шаге 3 нужно выполнить не более и операций слон!ения и и операций сравнения, чтобы получить временные пометки.
На шаге 1 нужно выполнпть еще не более и сравнений, чтобы получить постоянную пометку. Таким ,5) Р и с. 10.1в образом, требуется самое большее Зи операций, чтобы пайти одну постоянную пометку. Так как в сети имеется и узлов, то для нахождения кратчайшей цепи потребуется самое больсиее Зи' операций.
Рассмотрим сеть, изображенную на рис. 10.1, где числа рядом с дугами выра!кают расстояния. Линии без стрелок обозначают неориентированные дуги; считаем, что у неориентированных дуг с1!! — — 11!!. Найдем кратчайшую цепь в атой сети. Вначале все дуги сети ке принадлолсат дереву: узлы Хс, Хз, 14!5 — сосеДние с Узлом Х,. ПРисваиваеп вРеменные пометки: (Ь;!в г)= (4, г) — узлу Х!в (3, г) — узлу Язв (1, г) — узлу Уз.
Так как ш1п(4, 3, 1)=1, то пометка (1, г) становится постоянпой пометкой узла Лсз, а дуга А,з становится дугой дерева. Значит, пока найдепа только одна дуга дерева А„. Теперь узлами, соседними с, деревом, являются в!в„всвз, Хз, Хз. Присваиваем им врбз!Оппыо пометки: 1 в!' = Ш1П (Ьв1, Ьвз+ е(з!) = П11П (4,1+ оо) = 4, Аввз: = Ш1П (Вв2, 1 вз + с(зз) = ш1П (3, 1 - ~~ ° 1) = 2, в вс = Ш1П (А в4в вввз 1-Е(54) = Ш1П (сов 1 + оо) = оо А в5: = ППП (Авв5в .Сввд+ СКЗ5) = Ш1П (ОО, 8) =8. 15.1, БРлтчлнвзие цепи 195 Наименьшей из этих пометок является Х;„следовательно, она становится постоянной, а дуга Ав, становится дугой дерева.
Теперь текущее дерево состоит из двух дуг. Продолжим вычисле- ния: Х,з»1 = пцп (Хз1з Х за+1111) = пцп (4, 2+ 2) = 4, Х;41=ш1п(Ь;4 Хвз+1(гв)=шш(со, 2+5) =7, Хв»1 =ш1п(Хз»з Хзвэ+4(м) = шш(8~ 2+ ос) = 8. Наименьшей из этих пометок является Х;1, следовательно, она становится постоянной, а дуга А„становится дугой дерева. Далее, Х„;1 =шш(Х„'», Х„1+»(и) =ш1п(7, 4+2) Хз»'=(Х;5, Хз»+4)15) =ш1П(8, 4+4) =6, =8.
Теперь Х„'4 становится постоянной пометкой, а дуга А,» — дугой дерева. Далее Х;11=ш1п(Х;1, Х,„+»1»1) =ппп(со, 6+4) =10, Хз51= ш1п (Хзв5в Хз»+»звв) = шш(8, 6+ос) =8. Теперь Х;5 стаповится постоянной пометкой, а дуга Ам или Авв может стать дугой дерева. Выберем Ам в качестве дуги дерева. Тогда Х,;11 =ш1П(Х'1, Ввв+1151) = ш1П (10, 8+1) =9. ~1Г ~~ ~14 (2а) а в задаче максимизации— ~11 Э~ ~1Ь (2б) 13в Следовательно, дуга Ав, становится дугой дерева, и на этом вычисления заканчиваются. На рис. 10.1 дуги дерева выделены жирными линиями, а пометки узлов указаны в скобках. Описанный выше алгоритм можно использовать для нахождения не только кратчайших цепей, но и цепей, удовлетворяющих другим критериям оптимальности.
Поэтому интересно определить, при каких критериях оптимальности этот алгоритм приводит к решению. Поставим в соответствие каждой дуге сети А»т произ вольное число д11. Пусть Ап, А15,..., Арз, А,1, — произвольная последовательность дуг, образующая цепь. Обозначим через СЦ (Э'1»в ..., др~) ЗНаЧЕНИЕ КРИТЕРИЯ ОлтнМаЛЬНОСтн На ЦЕПИ Ап, А11,..., АР1 из узла Хв'1 в узел Хв'1, а через 615 (д11,..., ..., 4р1, д~») — значение критерия оптимальности на цепи Ап, А11, ..., Арзь Азл из узла Л11 в узел Хв'5.
Если в задаче минимизации критерия оптимальности выполняется условие 199 ГЛ. 1О. БРЛТЧЛЙШИК ПИПИ И ИОТОКИ МИНИМЛ.И НОЙ СТОИМОСТИ то для решения задачи можно использовать описанный выше алгоритм. В частности, если д11 — — й1Т и ищется кратчайшая цепь в сети, то 011 (КИ1 ° ° ° 1 Крт) = 011 + К1» + + йр19 (2) 61» (д11, ..., урн ят») = д11 + л1» +... + Ирт + д1». (4) Так как А1Т ~) О, то из (3) и (4) следует условие (2а).
Приведем еще один пример, когда выполняется условие (2). Пусть д„— это дуговые пропускные способности ды. Требуется найти цепь, через которую моя1но пропустить наибольший поток (задача о пути с максимальной пропускной способностью П04)). В этом случае 0'Ц (л11~ ° ° ~ Ярд И11л (0111 К»ь ° ° ° ~ Яр3) П1» (011 ° ° еи й~») = ""1" (И11~ й1»в ° ° 1 Крт~ й») Условие (2б) здесь выполняется.
Для того чтобы применить описанный выше алгоритм, следует в качестве временной пометки Б;» принять величину максимального потока, который можно пропустить из ДГ, в 11' », 1 выражение (») следует заме- Е г Л нить на следующее: 1;»: =шах(1;», шш(й.„, д„»)). к б 2 т В качестве постоянной по- 9 5 метки Ь,» следует взять мак- 3 4 симальную из временных пометок Е ~». Аналогичные изменения в алгоритме следует проводить при решении других задач, удовлетворяющих условиям (2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
