Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 38
Текст из файла (страница 38)
Однако не все так,просто, как кажется, поскольку условия оптимальности включают в себя также условие сохранения потока. Поэтому если поток по некоторой дуге (1, 1) увеличивается (или уменьшается), то ~в инцидентных ей узлах нарушается условие сохранения потока. А для того чтобы оно не нарушалось, необходимо найти другой путь из узла г' в узел ( (или из ( в 1', если поток уменьшается). Дуга (г', 1) и этот путь нз 1 в г вместе образуют цикл. Изменение потока по циклу не влияет на сохранение потока ни для какого узла. Путь из 1 в ( следует выбрать так, чтобы, во-первых, ни одна бездефектная дуга не стала бы дефектной и, во-вторых, ни одна из дефектных дуг не стала бы более дефектной. Таким образом, необходимо иметь процедуру, позволяющую определить, каким образом следует изменить потоки по всем рассматриваемым дугам и какой путь следует выбрать.
Описание такой процедуры, называемой процедурой расстановки пометок, приводится ниже. 3.5. ПРОЦЕДУРА РАССТАНОВКИ ПОМЕТОК 1. Если для того чтобы дуга (г, 1) перестала быть дефектной, поток по ней следует увеличить, то она находится в одном из состояний рь 6~ или аг. Приписать узлу г пометку ~дь 1+1, кото- 234 Глава 3 рая означает, что узел ) может получить дг дополнительных единиц потока пз узла й Если дуга находится в состоянии ш, то дг определить равным ппп(дь Ьц — )и], а если в состоянии р1 нли б~'>, то гп определить равным ппп (дь (Уп — ~п]з~, 2.
Если поток по дуге (г', )) следует уменьшить, то она находится в одном из состояний Вз, бз нли аз. Приписать узлу ( пометку [дь ) ], которая означает, что поток, выходяший из узла й и входящий в узел ), может быть уменьшен на величину дь Если дуга находится в состоянии аз или йзз>, то йч определить равным ппп~дь ~п — Еп], а если — в состоянии бш то д; определить равным ш1п~дь ~;у — Уп]. 3. Если дуга (г', )) находится в одном из состояний а, р или б, то она не является дефектной, и поток по ней изменять не надо. Исключение составляет состояние р, для которого поток можно увеличить или уменьшить таким образом, что ни одно нз условий не будет нарушено.
Как только обнаруживается, что дуга (г', )) является дефектной, узел й или ) помечается по правилу 1 или 2. Если изменение потока по дуге, указанное с помошью пометки, возможно, то дуга может стать бездефектной. Однако, как отмечалось выше, для того чтобы не нарушалось условие сохранения потока, необходимо найти дополнительный путь нз ( в ) (или нз у в с).
Для определения приращений потоков дополнительного пути следует пометить каждый его внутренний узел. Рассмотрим произвольную дугу (х, у) дополнительного пути. Эта промежуточная дуга будет находиться в одном из перечисленных выше девяти взаимно исключающих состояний. Если она я~вляется дефектной, то поток следует изменить таким образом, чтобы ее дефект не увеличился. Аналогично поток по бездефектной дуге должен измениться так, чтобы она не стала дефектной. Предположим теперь, что мы остановились на некотором помеченном узле хл> и хотим пройти по дуге из узла х (помеченного) в узел у (непомеченный). )~с Ох~-(у у Просмотр обратной дуги Просмотр прямои дуги н Поскольку с=б, то, для того чтобы дуга перестала быть дефектной, поток по ней можно увеличить кзк до нижней, твк н до верхней грвннцы.
з~ В результате применения данного правила дуга (й !) перестает быть дефектной, в дефекты остальных дуг последовательно уменьшаются, м Справедливо замечание, аналогичное замечанию !. О Поскольку этот процесс всегда начинается в заданном узле, то первоначально однн узел всегда является помеченным. Алгоритм дефакто Из помеченного узла мы пытаемся пройти по всем прямым н обратным дугам, инцидентным ему. При некоторых состояниях дуги узел на другом ее конце может быть помечен. Аналогично из одного узла можно пометить несколько различных узлов, хотя для продолжения процедуры достаточно пометить только один узел.
После завершения процесса расстановки пометок из данного узла этот узел помечается как просмотренный, Затем движемся к помеченному, но непросмотренному узлу. Хотя вы помечаете непросулотренньй узел на инцидентных дугах, чам Таблица З.4. Процедура расстановки пометок ддя прямой дуги с„„ "т с„= с„ т т т Предположии, что узлу х приписана палатка)ежи*) Можно ли пометить ужп У т если У вези чгнпс по гокзуж пРиведет к Увеличению дефекта дУги (х У) то У не ноже» выгь помечен из х Сос панне Мажет лн пт Отсу»с кует у Еьть по еиут (х,у) с Р ГР л пзюе тт ллчече т Да с>0 Нет В резуль~а~е увеличение потока дуга станет дефектное Поток ложат быть увеличен до и Поток не может выть увеличен поток на пожег сыть увеличен Поток может сыть увеличен до Е с=О Да Да Дв Нет с<0 с>0 с=о с<0 с) 0 б аз рт бт аз нет Поток может сыть увеличен до ц Поток может сыть увеличен до и Увеличение потока приведет к увеличению дефекта дуги Нет Нет Г) и Нвт с=о Увеличение потоке приведет к увеличению дефекта дуги Нат с<о Г>и нвт Увеличение потока приведет к увеличению дефекта дуги Нвт Резюме, приписать узлу у поиетку )ох, х чй если с Р > 0 и ûР< 1 Р', ЕР тттзв ьо» д*з Г Р .......
с„„<о и Г»Р< и.л; ' * ел птзп зо» и»Р Г»Р) следует спросить: «Как изменить поток по этой дуге — уменьшить или увеличить?» После ответа на этот вопрос можно указать приращение потока по этой дуге. Затем вы можете продолжить движение из просмотренного узла в помеченный, но непросмотренный узел. Величина приращения потока по дуге определяется по состоянию этой дуги посредством решающих правил, описанных ~в табл. 3.4 и 3.5.
Таким образом, должна быть решена следующая задача Выбирается дефектная дуга е)', )), поток по которой следует из- Г<и Г=и Г=и Г<х Г<й Г<и Г>ь Да Нет Нвт Да Да Дв Нет Гдово 8 Тлблица 3.5. Процедура расстановки пометок для обратной дуги (у,х1е В «„с,„ Ут ° г„=с„ь Предположим,итоуьпухприписпнепометкпм„,х*) Можнопипаметитьуьеп > т Если Умень пение потакать „понаедет к Уеелинению дефекта дУ пи тУхв то У не мажет Еьль поменен иь х менить так, чтобы она,перестала быть дефектной.
Для выполнения условия сохранения потока определяется дополнительный путь из узла 1 в узел 1 (или из ( в 1), и затем потоки по дугам этого пути изменяются в соответствии с последней пометкой д; (или ду). Допустим, что мы передвигаемся из узла / в узел 1, проходя по прямым и обратным дугам через просмотренные узлы. Напомним, что изменение потока по дуге не допускается, если оно приведет к тому, что (1) бездефектная дуга станет дефектной или (2) дефект дуги увеличится.
Следовательно, может возникнуть такая ситуация, что мы достигнем некоторого узла, из которого дальнейшее движение невозможно. Может показаться, что в этом случае нельзя построить путь из / в ( и, следовательно, решения исходной потоковой задачи не существует. При этом бесполезно переходить к другой дефектной дуге и на. чинать процесс заново, поскольку в конечном счете, до того как 237 Алгоритм дефекта может быть найдено оптимальное решение, вышеуказанная дуга должна быть выбрана. Данная ситуация называется непрорывом.
К счастью, при возникновении нвпрорыва существует еще один способ поиска оптимального потока. Напомним, что состояние дуги однозначно определяется величиной со=си+и; — пг и поэтому оно может измениться в результате изменения значений и. По определению двойственной задачи, которое было дано выше, каждому узлу ставится в соответствие некоторая переменная и.
Поэтому для потоковой задачи с и узлами существует ровно и двойственных переменных и. При возникновении непрорыва напрашивается следующий вопрос: значения каких переменных и следует изменить, чтобы построить путь из узла 1 в узел 1 (или из 1 в 1, если поток уменьшается)? Напомним, что мы начали движение из узла 1 и проходили по прямым и обратным дугам через просмотренные узлы, пытаясь достичь узла й По мере нашего продвижения узлы, через которые мы проходим, помечаются ло описанным ~выше правиламо.
Следовательно, при возникновении непрорыва существуют два непересекающихся множества узлов: 1) просмотренные помеченнь|е узлы и 2) непомеченные узлы. Очевидно, что в ситуации непрорыва нас интересуют только те узлы, с помощью которых мы сможем завершить продвижение из узла 1 в узел й Для продолжения процесса мы должны передвигаться из просмотренного помеченного узла (поскольку из него можно по крайней мере продвинуться дальше) в непомеченный узел. Поэтому необходимо рассмотреть только те числа п, которые соответствуют дугам, соединяющим помеченные узлы с непомеченными.
Обозначим множество всех помеченных узлов через А, а множество всех непомеченных узлов — через А. Если мы остановимся на некотором просмотренном помеченном узле х и посмотрим в сторону непомеченного узла у, то увидим либо прямую, либо обратную дугу. В первом случае поток может протекать из А в А, во втором — нз А в А. Случай 1. Пусть  — множество всех дуг, которые исходят из узлов, принадлежащих А, входят в узлы нз А и для которых с)0, а поток не превосходит верхней границы. Случай П. Пусть  — множество всех дуг, которые исходят нз узлов, принадлежащих А, входят в узлы из А и для которых с(0, а поток не меньше нижней границы. Поскольку значение с можно вычислить для любой дуги из множеств В и В, то процесс нужно продолжить следующим образом: 1.
Случай 1: с)0. о Либо узел 1, либо 1 принадлежит этому множеству помеченных узлов, поскольку один из ннх бмл помечен первоначально. Глава 3 Определить ~1=ш1п[с в1', если ВФв, и ь1=со в противном слув чае. 2. Случай 11: с(0. Определить ьт=ш1п[ — свл), если ВФи, и ьз=оо в противном в случае. 3. Пусть ь=ш[п[ьь ьз).
4. Для каждого узла ЙенА изменить соответствующее узловое число пм прибавляя к нему величину ь. 5. Сохранить ~все предыдущие пометки. Затем, возвращаясь к процедуре расстановки пометок, продоажаем выполнение процесса. Если в результате выполнения описанных, выше шагов изменится состояние по крайней мере одной дуги, ведущей из множества всех помеченных узлов в множество всех непомеченных узлов, то процедуру расстановки пометок следует продолжить до тех пор, пока (1) не возникнет прорыв или (2) вновь не возникнет непрорыв.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
