Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 214
Скачиваний: 0
10.3. ДЕКОМПОЗИЦИОННЫЙ АЛГОРИТМ |
203 |
при всех дальнейших вычислениях останется (i, j) = j и (/, к) = к. Таким образом, выражение (2) правильно указывает, что в крат чайшей цепи за узлом N t идет узел Nj, а за узлом Nj — узел iVft. Теперь заменим исходную кратчайшую цепь из N p в N q другой, которая имеет ту же длину, что и исходная, но меньшее число узлов, т. е. введем новую базисную дугу A ik длины dl} + сД. Продолжая рассуждения рекуррентно, получим требуемое утверж дение.
Рассмотрим еще одну задачу [109]. Пусть имеется сеть с про пускными способностями дуг Ъц. Назовем пропускной способ ностью пути из узла Np в узел N q величину наименьшей из про пускных способностей дуг этого пути. Путь из N p в N q будем назы вать путем с максимальной пропускной способностью, если его пропускная способность не меньше, чем пропускная способность любого другого пути из N p в N q. Тернарная операция, аналогич ная введенной в этом параграфе операции (1 ), может быть исполь
зована для нахождения путей с максимальной пропускной спо собностью между всеми парами узлов сети. В этом случае тернар ная операция имеет следующий вид:
bih: = max [biA, min (bi}, bJk)] |
(3) |
для всех i, к Ф ], vi проводится последовательно для j |
— 1,2, . . . |
. . ., п.
Вместе с вычислением матрицы bih вычисляется справочная матрица размера т X п, аналогичная справочной матрице, рас смотренной выше. Элемент (г, к) этой матрицы полагается сначала равным к, а затем
(г, Д если bik < min (Ьц, bJk),
(г, к), если bih> min (Ьц, bJh).
10.3. Декомпозиционный алгоритм (Ху |1 И ], [113J)
Очень часто сеть не является сильно связной, т. е. состоит из менее чем п (п — 1) дуг. В этом случае соответствующая матри ца расстояний имеет много элементов, равных бесконечности. Это обстоятельство используется в декомпозиционном алгоритме, рассматриваемом ниже. Введем сначала несколько новых понятий.
Рассмотрим некоторое подмножество узлов в сети и обозначим его буквой А. Пусть X — некоторое другое подмножество узлов. Назовем множество X множеством, отрезающим А, если оно обладает следующим свойством: при удалении из сети множества X вместе со всеми инцидентными дугами сеть распадается на две несвязные компоненты, одна из которых содержит все узлы мно жества А и только эти узлы. Множество X, отрезающее А, назы вается минимальным отрезающим множеством, если никакое
204 г л . 10. К РА ТЧА Й Ш И Е Ц Е П И И ПОТОКИ М И Н И М А ЛЬН О Й с т о и м о с т и
собственное подмножество X не обладает указанным свойством. Ясно, что множество всех соседних с А узлов является минималь ным множеством, отрезающим А.
Сначала рассмотрим декомпозиционный алгоритм в его простей шей форме, а именно покажем, как разложить сеть на две части. Предположим, что наша сеть N разбита на три множества узлов:
N = A U X U В, |
где X — минимальное |
множество, |
отрезаю |
щее А. Обозначим через | А | мощность множества А. |
Присвоим |
||
узлам из множества А индексы 1 , 2 , . . . , |
| А |, а узлам из X — |
||
индексы | Л | + 1, |
\ А | + 2, | Л | + | X |
|. Тогда соответствую |
|
щая матрица расстояний будет иметь вид, представленный в таб
лице 10.4, причем Daa = |
[djj], |
где N t 6 A, |
Nj 6 A, DAB = [йгД |
|||
где N t £ A, Nj £ В и т. д. В |
начале вычислений все |
элементы |
||||
Dab и D Ва равны бесконечности. |
|
расстояний |
|
где |
||
Мы ввели обозначение Da$ для матрицы |
[dtj], |
|||||
N i £ a и Nj 6 Р- Иногда удобно использовать символ dap |
для |
обо |
||||
значения одного из элементов матрицы Daр. |
|
|
|
|||
|
Таблица |
10.4 |
|
|
|
|
D a a |
d a x |
D a b |
|
|
|
|
d x a |
Dxx |
d x b |
|
|
|
|
D b a |
DBx |
D B b |
|
|
|
|
Введем новое понятие — условно кратчайшая цепь. Цепь назы вается условно кратчайшей, если она является кратчайшей при условии, что все узлы этой цепи принадлежат некоторому задан
ному |
подмножеству узлов сети. Кратчайшее |
расстояние между |
Nt и |
Nj обозначим d*) (при этом кратчайшая |
цепь из Ni в Nj |
может содержать любые дуги сети). Длину условно кратчайшей цепи из Ni в Nj обозначим d*j (у), где у — то подмножество, которо му должны принадлежать узлы этой цепи. Матрицу условно
кратчайших расстояний |
[d*j(y)], |
где |
N t £ a, Nj £ р, |
обозначим |
||||||
Пар (у), |
а |
ее |
элементы —d£p(y). |
Так |
как |
вся |
сеть |
обозначена |
||
буквой N, |
то d*j{N)—d*j. Если |
известно, |
что |
кратчайшая цепь |
||||||
лежит в множестве у, |
то |
|
|
|
|
|
|
|||
|
|
|
|
|
d^(y) = d^(N). |
|
|
(1) |
||
Введем обозначение |
А = А ЦХ , |
В — В\]Х. Будем считать, что |
||||||||
исходная сеть образована из двух сетей, |
перекрывающих друг |
|||||||||
друга. |
Первая |
из этих |
сетей, называемая |
Я-сетью, |
состоит из |
|||||
10.3. ДЕКОМПОЗИЦИОННЫЙ |
АЛГОРИТМ |
205 |
узлов Ni, принадлежащих А, и дуг Aij, |
где N t, N j £ A . |
Вторая |
сеть, называемая 5-сетыо, состоит из узлов АД, принадлежащих 5, и дуг A kl, где АД, N ^ B .
Сначала выполним тернарные операции в А-сети. В результате получим условно кратчайшие цепи между всеми парами узлов
A-сети. В частности, получатся условно кратчайшие расстояния между всеми парами узлов из X. После этого выполним тернар ные операции в 5-сети, причем в качестве расстояний между узла ми из X возьмем условно кратчайшие расстояния, найденные ранее при вычислениях в A-сети. Затем выполним тернарные
операции снова в А-сети. Алгоритм декомпозиции для двух пере крывающихся сетей основан на следующей теореме.
Теорема 10.1. Пусть |
N = А \ ) Х \ } В , причем удаление мно- |
||
зкества X делает сеть несвязной. Пусть найдены условно кратчай |
|||
шие расстояния Dxx (А ). |
Тогда кратчайшие расстояния между |
||
любыми двумя узлами В-сети могут быть получены, если тернар |
|||
ные операции выполнять только в В-сети. (Заметим, |
что А = |
||
= N - В . ) |
|
|
|
Д оказательство. Е сли |
кратчайшая |
цепь лежит |
целиком |
в множестве В, то d%B (N) |
= d%B (В), т. |
е. достаточно выполнить |
|
тернарные |
операции |
только |
в |
|
А |
л |
а |
||||||
5-сети. |
|
|
|
|
|
|
|
|
|
||||
Рассмотрим |
теперь |
случай, |
|
|
|
|
|||||||
когда |
кратчайшая |
цепь |
|
имеет |
|
|
|
|
|||||
несколько участков, лежащих в |
|
|
|
|
|||||||||
множестве А. Символически этот |
|
|
|
|
|||||||||
случай |
изображен на |
рис. |
1 0 .6 . |
|
|
|
|
||||||
Рассмотрим |
кратчайшую |
цепь |
|
|
|
|
|||||||
из N p |
в N q, |
скажем |
из АД в N e. |
|
|
|
|
||||||
Так как эта цепь начинается и |
|
|
|
|
|||||||||
кончается |
в 5 , |
а X является мно |
|
|
|
|
|||||||
жеством, отрезающим 5 , то любой |
|
|
|
|
|||||||||
участок рассматриваемой цепи, |
ле |
|
|
|
|
||||||||
жащий |
в |
А, |
должен |
начинаться |
|
|
|
|
|||||
и кончаться |
в множестве |
X. |
На |
участка: |
из АД в N 3 и из Ni |
||||||||
рис. |
1 0 .6 |
изображены два |
таких |
||||||||||
в АД. |
Если известны величины d*3 (А) |
= d*3 (N — 5) и d*3 (А) = |
|||||||||||
= d*&(N — 5), |
то можно |
считать, |
что именно в 5-сети имеется |
||||||||||
две |
дуги: |
А 23 |
длины d*3 (N — B) |
и |
А 45 |
длины |
d*5 (N — В). |
||||||
Тогда |
кратчайшая |
цепь |
из |
Ni |
в |
N e состоит |
из следующих |
||||||
частей: цепи |
из N t в |
N 2, дуги А 23, цепи из N 3 в АД, дуга А 45, |
|||||||||||
цепи из N 5 в N q, причем все эти части лежат целиком в 5-сети
206 гл. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ
Таким образом, при нахождении кратчайшей цепи достаточно рассматривать только 5-сеть. Заметим, что проведенные рассуж
дения не зависят от числа участков цепи, лежащих в А.
Ясно, что теорема остается справедливой, если в ее формули ровке поменять местами А ж В. щ
Введем теперь одну специальную операцию над матрицами, которая будет использоваться в декомпозиционном алгоритме.
Заметим, что, для того чтобы попасть из некоторого узла N t 6 А в некоторый узел N k 6 В, необходимо пройти по крайней мере через один узел Nj 6 X. Если перебрать все цепи, проходя
щие через каждый из узлов Nj £ X, и выбрать среди них кратчай шую, то в результате, естественно, будет найдено кратчайшее расстояние d*k. Таким образом, при фиксированных i и к наде выполнить следующую операцию:
4 = т ш ( ^ + 4 ), |
/ = 1 , . . . , р , |
Ni £ A, |
N k £B, |
(2 ) |
||
s |
|
|
|
|
|
|
где р —мощность |
множества X. |
|
имеют размеры |
|||
Пусть матрицы расстояний DAx(N) и А г в ( А ) |
||||||
соответственно па х р |
и |
р х щ • Операция |
(2) напоминает |
опера |
||
цию умножения |
двух |
матриц, в которой |
символ |
« X » заменен |
||
символом «4-», |
а суммирование заменено взятием минимума. |
|||||
Будем называть операцию (2) композицией матриц. |
|
|||||
Общее число сложений при выполнении всех операций (2) |
||||||
равно па х пь х |
р; таково же общее число сравнений. |
|
||||
Сформулируем теперь декомпозиционный алгоритм для случая |
||||||
двух перекрывающихся |
сетей. |
|
|
|
||
Ш а г 1. Выполнить в сети А все тернарные операции приме нительно к матрице
А А А |
А а х |
_ А х а |
Вхх\ |
В результате выполнения этого шага получим матрицы D*AA(A)r
Вах (А), DxA{A), Dx x (A).
Ш аг 2. Выполнить все тернарные операции применительно к матрице
Вхх {A) DXB
_Авх Авв_
В результате по теореме 10.1 получим Dxx(N),
A b b ( X ) .
D x b ( N ) , D%x(N)t
|
|
10.3. ДЕКОМПОЗИЦИОННЫЙ АЛГОРИТМ |
207 |
|
Ш а г |
3. |
Выполнить все тернарные операции применительно |
||
к матрице |
|
|
|
|
|
|
~D*a a (A) |
D*aX {A) |
|
|
|
D%a {A) |
D*x x {N)_- |
|
В результате по теореме ЮЛ получим DA±(N), DAX(X), DXA(N), |
||||
DXX{N). |
|
|
|
|
Ш аг |
4. |
Используя операцию (4), получить DAB(N) и DBA(N). |
||
Подсчитаем число операций сложения, требующихся для выпол |
||||
нения этого алгоритма. (Операций сравнения столько же.) Для
простоты будем считать, что |
при |
вычислении |
матрицы размера |
|||||||||||||||
п X п требуется п3 операций сложения, |
а не п (п — 1 ) (п — 2 ). |
|||||||||||||||||
На шаге 1 алгоритма требуется выполнить ( | А | + |
| X |
|)3 |
опера |
|||||||||||||||
ций, |
на |
шаге |
2 — ( | В | + |
| X |
|)3 |
операций, |
на |
шаге 3 — |
||||||||||
( | А | |
+ |
| X |
|)3 |
операций, на шаге 4 |
— 2 |
| А |- | X | - | В | |
опера |
|||||||||||
ций. |
Таким |
образом, |
общее |
число |
операций |
|
сложения |
равно |
||||||||||
2 |
(| А | + |
| X |)3 + |
(| |
В | + |
| X |)3 |
+ |
2 | А |. | X |
|- ! |
В |. |
Общее |
||||||||
число операций сложения, если выполнять тернарные |
операции |
|||||||||||||||||
в |
общей |
сети |
N, |
не |
используя декомпозиционного алгоритма, |
|||||||||||||
равно (| А | |
+ |
| X |
| + |
| В |)3. |
Положим, |
что | А | = |
| В |. Тогда |
|||||||||||
использование |
декомпозиционного |
алгоритма |
позволяет |
умень |
||||||||||||||
шить |
общее |
число |
операций |
сложения на величину |
5 | А \3 |
|
||||||||||||
+ |
| А |2' | X |
| — 3 |
| А |-1 X |
|2 |
— 2 |
| X |3. Таким образом, |
деком |
|||||||||||
позиционный алгоритм уменьшает объем вычислений при |
| А ) |
> |
||||||||||||||||
> |
I * |
I- |
|
|
|
|
|
|
вычислений уменьшается на вели |
|||||||||
|
Если | + |+=|.В |, то объем |
|||||||||||||||||
чину 3| Л | . | В | . (| Л | + |
| В | ) - | Л I3 — 3 | Л |2 . | Х | + |
|
4 | Л | . | В | . | Х | |
— |
||||||||||||||
— 3 1А\-\ X !2 — 2 1X |3. |
Например, |
если |
\ В \ = |
- ^ п , |
| А \ = - ^ |
п, |
||||||||||||
I ^ I = |
То п’ то °^ъем вычислений уменьшается на |
|
п3 |
действий. |
||||||||||||||
|
В |
том случае, |
когда сеть |
имеет |
большие размеры |
и |
«слабо» |
|||||||||||
связна, удобно разлагать сеть на несколько перекрывающихся сетей. Пусть, например, сеть можно разбить на 4 перекрываю щиеся подсети. Матрица расстояний для этой сети имеет вид, представленный на табл. 10.5, где незатемненные области состоят из элементов dtj — оо.
Чтобы построить матрицу расстояний такого вида, поступают следующим образом. Некоторое подмножество узлов выбирают в качестве А. Минимальное множество, отрезающее А, выбирают
в качестве |
Х А. |
В качестве В можно взять некоторое |
множество |
||||
(не обязательно |
минимальное), |
отрезающее |
А \ ] Х а ,& |
в |
качестве |
||
Х в — минимальное множество, |
отрезающее |
A [J ХА (J В. (Заме |
|||||
тим, что |
минимальным |
множеством, отрезающим В , |
|
является |
|||
^ а 1)Хв.) |
В качестве С возьмем некоторое множество, |
отрезаю |
|||||
щее + (J ХА U В U Х в , |
а в качестве Хс — минимальное мно |
||||||