Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 36
Текст из файла (страница 36)
Шаг 2. Выполнить все тернарные операции применительно к матрице с Рхх(А) Рхв ~ Рвх Рвв1 В результате по теореме $0Л получим Рххх(!У), Ров(Л) Рлх(!»), Рвв Р) ю.з. лзкомпозипионпыи ллгогнтм 207 Ш а г 3. Выполнить все тернарные операции применительно к матрице В результате по теореме 10.1 получим Р„*а(У), Р„*х(<<<), Рх„,(<«'), Рхх(Х).
Шаг 4. Используя операцию (4), получить Р*,,в(Ф) и Рв„(У). Подсчитаем число операций сложения, требующихся для выполнения етого алгоритма. (Операций сравнения столько же.) Для простоты будем считать, что при вычислении матрицы раамера и х и требуется и' операций сложения, а не и (и — 1)(и — 2). На шаге 1 алгоритма требуется выполнить (~ А ~ + ) Х ~)з операций, на шаге 2 — (! В ~ + ~ Х ~)з операций, на шаге 3— (! А ~ + ! Х!)з операций, на шаге 4 — 2 ! А 1 ~ Х ( ~ В ~ операций. Таким образом, общее число операций сложения равно 2()А ~+~ХО»+()В~+)Х~)в+2~А ! ~Х~ ~В!.
Общее число операций сложения, если выполнять тернарные операции в общей сети Л, не используя декомпозиционного алгоритма, равно (~ А ~ + ~ Х ~ + ~ В !)з. Положим, что ! А ~ = ~ В (. Тогда использование декомпозиционного алгоритма позволяет уменьшить общее число операций сложения на величину 5 ~ А )з-(- + ! А !' ! Х 1 — 3 ) А ! ) Х !' — 2 ! Х ~з. Таким образом, деком- позиционный алгоритм уменьшает объем вычислений при ) А ~ ) ~~Х~. Если (А)~1В), то объем вычислений уменьшается на величину 3)А).~В~ ((А ~+~В~) — ~А (з — 3)А!'~Х~+4~А! ~В~ !Х!— — З~А~ ~Х" ,— 2~Х~». Например, если ~В)= — и, )А~= — и, 10 1 494 з ~ Х~ = — и то объем вычислений уменьшается на — и' действий.
10 1000 В том случае, когда сеть имеет большие размеры и «слабо» связна, удобно разлагать сеть на несколько перекрывающихся сетей. Пусть, например, сеть можно разбить на 4 перекрывающиеся подсети. Матрица расстояний для атой сети имеет вид, представленный на табл. 10.5, где неаатемненпые области состоят из алементов <зп = оо.
Чтобы построить матрицу расстояний такого вида, поступают следующим образом. Некоторое подмножество узлов выбирают в качестве А. Минимальное множество, отрезающее А, выбирают в качестве Х„. В качестве В можно взять некоторое мноя<ество (не обязательно минимальное), отрезающее А () Х„, а в качестве Хз — минимальное множество, отрезающее А () Хл() В.
(Заметим, что минимальным множеством, отрезающим В, является Хл () Хв.) В качестве С возьмем некоторое множество, отрезающее А () Х„() В () Хв, а в качестве Хс — минимальное мно- лайз Г:1. 10. КРАТЧАЙШИЕ ЦЕНИ П ПОТОКИ МИРЛ1МА;И*НОЙ СТОИМООТИ жество, отрезающее А О Х,, () В () Хв () С. Этот процесс продолжается до тех пор, пока сеть не окажется разлон1енной на требуемое число перекрывающихся сетей. Соть, соответствующая табл. 10.5, разложена на 4 перекрывающиеся сети: А=А() ХА~ В=ХА()В() Хв С=Ха()С() Хс и Н=Х ц)0. Таблица 10.й лт Ул 0 Х С Л' Ю Сформулируем общий декомпозициопный алгоритм для случая, когда исходная сеть рааложена на т перекрывающихся сетей: А, В, ..., С, Й. Ш а г 1. Выполнить терпарные операции последовательно в т — 1 сетях А, В, ..., С, причем полученные для некоторой сети условно кратчайшие расстояния должны использоваться для вычислений в последующей сети.
То есть, например, прк выполнении тернарных операций в сети В= ХА О В () Хз матрица расстояний,0х х должна быть эамонепа матрицей Щ х (А). Заметим, что мы можем пользоваться теоремой 10,1, рассматривая по очереди каждое иа множеств А, Л цХА() Хв, ... в качестве А, фигурирующего в формулировке теоремы 10Л. При этом в качестве мнолцества В из тооремы 10Л возьмем соответственно множества В() Хв О...
ОН, С() Хс() ° . () Н, .... Тогда одна за другой будут получаться следующие матрицы условно кратчайших расстояний: В-*А(Л), Щ- (Л () В), ..., Щ б (А (! 6 () ... ... ()С). 111аг 2, Выполнить терпарные операции в т сетях в следующей последовательности: Й, С, ..., В, Л, причем полученные 10АЬ ДЕКОМПОЗИЦИОПНЫИ АЛГОРИТМ 209 для некоторой сети кратчай1пие расстояния использовать для вычислений в следующей сети. То есть, например, матрица расстояний Вх х (У вЂ” В) должна быть заменена матрицой Вх х (11'). По теореме 10.1 будут получены следующие матрицы расстояний: ЙЙ( )~ ОО( )~ ' ' '~ вз( )~ АА( )' Ш а г 3.
С помощью операции (4) композиции матриц найти кратчайшиэ расстояния мел'ду всеми парами узлов, не леи1ащими одновременно ни в одном из множеств Л, В,..., Й. Будем испольаовать обозначение Л Й1 Хи ~ В для операции композиции матриц, где 1У1ЕЛ, 1УтеХА, 11'А Е В. Должны быть выполнены операции А Щ ХА ® В и В ® ХА ® А, по для простоты будем записывать только одну из них.
Операции композиции матриц должны выполняться в следующем порядке: ЛЮХАЕВ0Х„ Л 0 ХА 0 ВВХвВС 0 Хс Л0ХАОВ0ХИ0СеХ,е00Х, А 0 ХА 0 . 0 ВЮХРЮС 0 ХО А 0 ХА 0 0 СЮ ХО1ВВ При этих вычислениях матрица Р"„х 111'), полученная при выполв ненни операции Л ®ХАЕВ 0 Хв, используется в .последующих вычислениях и т. д. Оценим число арифметических действий в этом декомпозиционном алгоритме для случая, когда [А[=-[В[= ... =[В[=1, а [Хи[=[Ха[= ...=[ВО[=6. Подсчитаелг,число операций сложения (таково же и число операций сравнения). Па шаге 1 число сложений равно (1л-6)'+(т — 2)(1 ', 26)з. На шаге 2— 2 (1+ 6)з (ж 2) (г ° 26)з На шаге 3— 2(г+(2г+6) — ' ... + [(т — 2)г, (т — 3)6)) 6(г — '6) — ,' + 2 [(т — 1) 1-1.
(т — 2) 6) 61 = и (т — 1) 116.+ + 2 (т — 1 ) (т — 2) 161 -[- (т — 2) (т — 3) бз Таким обраао . общее число операций сложения равно (2т — 1) гз -[- (шз + 11т — 15) 116 -[- [ (2тз 1 18т 35) гбзл (тз [ 11т 23) бз (5) Если, не испольауя декомпоаиционного алгоритма, выполнить тернарные операции непосредственно на всей сети, то общее 14т хт 310 ГЛ. 1О. КРАТЧАЙШИЕ ПИПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ число операций сложения будет равно (вс~ + (вс — т) 6)' (6) При достаточно больших сп выраэкение (5) близко к вс'6 (8 + 6)а, а вырансение (6) — к т'6 (й + 6)а.
'Гаким образом, прн и — ~ со отношение выражений (5) и (6) стремится к —. о (1+0)м ' ою Р н с. $0.7. После разложения (декомпозиции) исходной сети на сети А, В,..., Н каждая ив них в свою очередь может быть разложена на меньшие сети, и этот процесс декомпоанцин может быть продолжен и дальше.
Заметим, что каждое из множеств узлов А, Х„, В, Х„... не обязано быть связным. В качестве множества А можно брать любое подмпожество узлов. После выбора А множество Х„определяется однозначно. В качестве множества В можно взять любое множество, отделяющее А () Х„; мноясество Х„определяется однозначно — это минимальное множество, отделяющее А О ХА Ц О Хв 10.3.
Дккомпозипиопный Алгогитм Описанная выше декомпозиция (разбиение) сети может быть названа линейной, так как при этом т пересекающихся подмножеств А, В,..., Н расположены как бы в линию (рис. 10.7 (а)). Можно рассмотреть декомпозицию сети, в которой подмножества А, В,..., Н поресекают друг друга произвольным образом (рис. 10.7 (б)). Полученное при этом разбиение сети можно получить с помощью линейной декомпозиции. Для этого надо ваять, например, Ае = Е, В"' = А ()Р, С* = В() С()Б, 0" = б, Е* = Й, рассмотреть линейную декомпозицию исходной сети Р и'с.
40.8. на сети А", В*, Сэ, Е* и затем осуществить линейную декомпозицию сети В* на две меньшие — А, Е, а сети Ее на три меньшие— В, С В. При произвольной декомпозиции сети число операций больше, чем при линейной. Б заключение параграфа обсудим одну идею, которая поясняет принцип декомпозиционного алгоритма. Пусть имеется сеть с и узлами, и надо найти в ней кратчайшие пути между р выделенными узлами, р ~ ~и. Будем говорить, что некоторая сеть с р узлами эквивалентна пс расстоянию исходной сети с л узлами, если кратчайшие расстояния между р (р — 1) парами выделенных узлов в обеих сетях одинаковы. На рис.
10.8 изображены две сети, которые эквивалентны по расстоянию относительно выделенных узлов У„Л'м Фм 7У,. Понятие эквивалентности по расстоянию может быть использовано для удаления из сети на некотором этапе вычислений тех узлов и дуг, которые не влияют на атом этапе на вычисления кратчайших расстояний. На рис. 10.9 приведены некоторые примеры сетей, эквивалентных по расстоянию. В частности, если сеть с 4 узлами, изображенную на рис. 10.9 (с), превратить в изображенную на этом же рисунке сеть с 3 узламн, то все кратчайшие расстояния между узлами ))г„Фю У, могут быть найдены в новой сети. Используя простые преобразования сети, изображенные на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
