Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 190

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

8. МЕТОД РАССТАНОВКИ ПОМЕТОК

145

это пропускная способность дуги, а второе — исходный поток по дугам. (Можно использовать в качестве исходного потока любые числа, удовлетворяющие условиям (1 ),

(2). В частности, можно было бы взять Хц = 0 для всех i, /.)

Ш а г

1.

Припишем узлу N s помет­

 

ку [s+, оо]. Узел

N s

имеет

2 соседних

 

узла.

Пометить

N 4 мы не

можем, так

 

как bsl — xsl

 

=

1

— 1 = 0 , и нет дуго­

 

вого

потока

 

xis >

0.

Узлу N 2 припи­

 

шем

пометку

[s+,

1 1 ,

поскольку bs2 —

Р и с. 8.4.

— xs2 = 2

—

1

=

1

и s (2 ) = min [е (а),

 

bs2 —

=

min (оо,

1 ) =

1 .

 

Теперь узел N s помечен и просмотрен, a N 2 помечен и не про­

смотрен.

 

имеет два непомеченных соседних узла, а именно N j

Узел N 2

и N t. Узел N t в данный момент не может быть помечен, а узел

Атj получает пометку [2~, 1],

поскольку xi2 = 1 >

0 и

е (1) =

= min (е (2),

xl2] = min (1, 1)

=

1.

Теперь

узел

N 2

помечен

и просмотрен, a

помечен и не просмотрен. Узел N { имеет толь­

ко один соседний непомеченный узел,

а именно N t. Узел N t дол­

жен получить

пометку [1 +,

1 1 ,

поскольку

е (t)

= min [е (1 ),

•Ьи — xlt] =

min [1 , 3 — 0 ] =

1 .

 

 

 

на рис. 8.5.

Результат

этой расстановки пометок изображен

Так как узел Атt оказывается помеченным, то переходим к шагу 2.

Ш а г

2. Так как пометка узла N t есть [1+,

1],

то увеличиваем

xit на 1.

В результате получаем x\t = ' xlt

+

l = 0 - j ^ l = l .

 

(2-,П

 

 

(1+,

Переходим к узлу обладающему пометкой [2“, 1], и уменьшаем х12 на 1. Получаем х'12 = х12 — 1 = 1 — 1 = 0 . Переходим к узлу

N 2, имеющему пометку [s+,

11, и прибавляем 1 к х ,г. Получаем:

x's2 = xs2 + 1 = 1 + 1 == 2.

Окончательный результат операции

изменения потока изображен на рис. 8 .6 .

10 Т. Х у

146

 

ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК

Ш а г

3.

Приписываем пометку [s+,

се] узлу N s. Теперь узлы

N 1 и iV2

не могут быть помечены, и узел N t оказывается непоме­

ченным.

Конец.

 

Сделаем

два замечания. Во-первых,

мы увеличиваем поток

(рис. 8.4), посылая единицу потока по следующему пу*ги, увеличи­

вающему поток: N s, A s2, N 2, A i2,

A iU N t. Если

бы не было

потока по дуге Л 12, то нельзя было бы послать поток

из N 2 в Л+

потому что A i2 — ориентированная дуга. Но когда уже имеется ненулевой поток по дуге Л 12, можно послать поток из N 2 в N t, и в результате новый и прежний потоки по этой дуге взаимно уничтожатся.

Во-вторых, здесь получается

минимальный разрез (X , X),

где X

— это единственный

узел N s, а X — три узла N if N 2, N

Заметим,

что (У, Y),

где

Y

= { N t,

N 2} — тоже

минимальный

разрез

с

пропускной

способностью,

равной

bsi

+ b2l +

b2t =

= 1 +

0

+ 2 = 3. Здесь

X с

Y.

Как уже

отмечалось

выше,

алгоритм расстановки пометок всегда дает такой минимальный

разрез (X, X), что X — наименьшее среди упорядоченных по включению подмножеств узлов.

Если пропускные способности b(j не являются все целыми числами, то алгоритм может не быть конечным и может даже сходиться не к максимальному потоку. Такой пример построен Фордом и Фалкерсоном [67]. Это показывает, что метод расста­ новки пометок не эквивалентен симплекс-методу для задач линей­ ного программирования. Так как задача о потоке в сети является частным случаем задачи линейного программирования, а симплексметод работает при любых действительных числах, то должен существовать алгоритм решения потоковой задачи, в которой пропускные способности дуг являются любыми действительными числами.

Перейдем к рассмотрению такой модификации метода расста­ новки пометок, которая применима для любых неориентированных

сетей с действительными пропускными способностями.

 

Ш а г

1.

Удалим из сети все дуги, для которых выполняется

xtj = btj)

такие дуги будем называть насыщенными

потоком.

(В самом начале нет насыщенных дуг, так как xi} = 0.)

Перехо­

дим к шагу 2 .

 

Ш а г

2.

Используя любые оставшиеся в сети дуги,

находим

с помощью метода расстановки пометок произвольный путь, уве­ личивающий поток; посылаем по нему максимально возможный поток. Если такой путь нашелся, 'то переходим к шагу 1; если же нет, переходим к шагу 3.

8.2. МЕТОД РАССТАНОВКИ ПОМЕТОК

147

Ш а г 3. Восстанавливаем в сети все ранее удаленные дуги (т. е. все дуги, насыщенные потоком). Находим некоторый путь из N s в N t, увеличивающий поток, и посылаем по нему максималь­ но возможный поток. Если такой путь нашелся, то переходим к шагу 1 ; если же нет, то алгоритм закончен и найденный поток —

максимальный.

Докажем, что этот алгоритм конечен и дает максимальный поток. При каждом изменении потока на шаге 2 по крайней мере одна новая дуга оказывается насыщенной потоком. После того как шаги 1 и 2 будут повторены друг за другом некоторое конечное

число раз, из сети будет удалено такое количество насыщенных дуг, что уже нельзя будет на шаге 2 получить поток с большей

величиной. Если при этом на шаге 2 использовать метод расста­ новки пометок, то будет помечено некоторое множество узлов X,

а все такие дуги А г;-, что N t £ X , N j £ X , будут насыщены потоком. (Заметим, что поток может идти по дуге в любом направлении.) Величина потока при этом равна

 

2

_ х ц —

2

_ Х м =

2

_ Ь ц —

2

h i 1)-

JVj£X; N f i X

N f i X , JVfe£X

N £ X , N j £ X

N f i X ,

X

После этого переходим к шагу 3 и восстанавливаем в сети все

насыщенные дуги.

Теперь можно пометить любой узел N h, кото­

рый принадлежал X на шаге 2 ,

если имеется дуга с xki > 0 , где

N г 6

X . Благодаря тому,

что в сети восстановлены насыщенные

дуги,

узел N t попадет в множество X

и величина потока в сети

возрастет. Затем мы снова перейдем к шагу 1, и когда опять вер­ немся к шагу 3, величина потока в сети будет снова равна разности

2 Ъц — 2 bhi- Но величина потока при этом изменится, следова-

г ,3 Ь.,1

тельно, в этот раз на шаге 3

суммы 2

Ъц, 2 bkt берутся по другим

множествам дуг (либо по

i j

k tl

тем же

самым множествам дуг, что

и в предыдущий раз на шаге 3, но некоторые из них проходятся в противоположном направлении). Так как в сети имеется конеч­ ное множество дуг и каждая дуга может быть насыщена потоком

в одном из двух направлений, то величина 2

btj — 2 bhi

может

 

г ,3

k ,l

 

*) Сумма 2

Ьц берется по тем дугам Aij, для которых Х г£Х,

Nj £X,

N j £ X

 

 

 

н я ; у >0 . Сумма

^ Ьм берется по тем дугам Aki,

для которых

N ^ ^ X ,

№

Ni £ X, и 0. —Прим, перев.

10*

148 ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК

принимать конечное множество различных значений. Каждый раз, когда мы возвращаемся к операции 3, величина потока при­

нимает одно из значений 2

Ьц — 2 ^ki- Поскольку каждый раз

i j

h , l

величина потока возрастает, то ни одно из этих значений не повторяется дважды. Таким образом, алгоритм конечен.

Этот же алгоритм можно использовать и в сетях с ориентиро­ ванными дугами, но доказательство этого факта довольно громозд­ ко *). Трудность заключается в том, что при осуществлении про­ цедуры изменения потока на шаге 2 поток по некоторой ориенти­

рованной дуге может взаимно уничтожиться с прежним, но ни одна дуга при этом не будет насыщена потоком. Поэтому нельзя утвер­ ждать, что на шаге 2 найдется по крайней мере одна новая дуга,

насыщенная потоком.

Теперь перейдем к изучению следующего вопроса: какое коли­ чество итераций в методе расстановки пометок требуется для нахождения максимального потока?

Каждый путь, увеличивающий поток, дает возможность увели­ чить величину потока по крайней мере на единицу. Если величина максимального потока равна v, то для нахождения максимального потока достаточно не больше чем v раз найти путь, увеличивающий поток. Предположим теперь, что мы умножили на 10 все пропуск­ ные способности дуг. Тогда величина максимального потока в новой сети будет равна 10и. Это означает, что для нахождения максимального потока в сети достаточно самое большее 1 0 ы раз

найти путь, увеличивающий поток. Следовательно, полезно было бы иметь такую верхнюю оценку количества итераций в процессе расстановки пометок, которая не зависела бы от величины макси­ мального потока, не известной до начала вычислений. Такая верхняя оценка была получена впервые Эдмондсом и Карпом 158]. Эта оценка справедлива и тогда, когда все пропускные способно­ сти дуг — действительные числа. Рассмотрим подробнее эти резуль­ таты 2).

Сделаем несколько замечаний и приведем модификацию метода расстановки пометок. Для, удобства будем считать, что сеть, имеющая п узлов, всегда содержит п (п — 1 ) дуг, хотя некоторые

дуги могут обладать пропускной способностью, равной, нулю. Если задан поток F в некоторой сети, будем использовать символ1*

1) Это утверждение не точно. Как показано

в работе [17*], в ориентиро-

1 ванных сетях с иррациональными пропускными

способностями дуг рассма­

триваемый алгоритм может не быть конечным. В этой же работе приводится [ модификация алгоритма, которая уже применима для лю.бых ориентирован- \яы х сетей.— Прим, перев.

2) В переводе исправлены имеющиеся в оригинале погрешности и вне­ сены уточнения, содержащиеся в работе Эдмондса и Карпа [58*], появив­ шейся после выхода в свет данной книги.— Прим, перев.

 

8.2. МЕТОД РАССТАНОВКИ ПОМЕТОК

149

N

(F) для обозначения этой сети вместе с текущим в ней потоком F.

В

сети N (F) дуга

может быть насыщена (х1} =

Ьц), и тогда

можно считать, что дуги А ц в сети «не существует», поскольку все

равно нельзя послать поток из узла N t в узел Nj

по дуге A tj.

Так как можно послать поток из N j в N t в сети N

(F), то можно

считать, что в N (F) имеется дуга Ац с пропускной способностью

Ьц — %ц. Например, можно считать, что на рис.

8.4 дуги A i2

не существует, а имеется дуга i 2) с пропускной способностью, равной 1. В дальнейшем, говоря о сети N (F), будем иметь в виду

Р и с . 8.7. Р и с . 8.8.

сеть, отличающуюся от исходной сети, в которой еще не было потока. Метод расстановки пометок, таким образом, порождает некоторую последовательность сетей: N (Fi), N (F2), . . ., N (Fm), где Fm — максимальный поток. Поуок Fk+l получается из пото­ ка Fk с помощью добавления в сеть N (Fh) некоторого пути, увели­ чивающего поток.

При описании метода расстановки пометок мы до сих пор не указывали, в каком порядке следует просматривать помеченные узлы. Будем теперь придерживаться правила «первым помечен ■— первым просмотрен». Так, в рассмотренном выше примере (рис. 8.4)

узел N z должен

быть просмотрен

перед

узлом

iVl5 так

как N z

помечен

раньше,

чем N t. При

использовании

правила

«первым

помечен

— первым просмотрен»

в

методе

расстановки

пометок,

каждый раз будет получаться увеличивающий поток путь, который содержит минимальное число дуг (если поток в сети еще не макси­

мален) *).

Сделаем еще одно уточнение. Если П 81, А 12, А 23, . . .

. . .,

A ht — некоторый путь, увеличивающий поток,

то определим

е (/ +

1 )

следующим образом:

е (/ + 1 ) = min [е (j) b}, j+ 1 —

— Xj,

j+ 1

+ xj+i, J. При таком

модифицированном

определении

пометки е (; + 1 ) по крайней мере одна дуга в пути,

увеличиваю­

щем поток, окажется насыщенной потоком. Рассмотрим сеть, изображенную на рис. 8.7, где числа рядом с дугами означают

х) В гл. 10 будет рассмотрен алгоритм Дийкстры решения задачи о крат­ чайшем пути в сети. В случае когда длины всех дуг равны 1, он сводится

к правилу «первым помечен — первым просмотрен». Отсюда

следует, что

это правило приводит к пути, содержащему минимальное

число дуг.—

Прим, перев.

 

Смотрите также файлы