1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 46
Текст из файла (страница 46)
Пусть функция разметки й (г'Х у) -~- В определена, как в алгоритме 5.5, а Ао обозначает (пХп)-матрицу с ໠— — 1(о„ог), Следующая лемма связывает вычисление, выполняемое алгоритмом 5.5, с вычислением замыкания Ао матрицы А в полукольце М„ (пХп)-Матриц над В. Лемма 5.11. Пусть б и Ао таковы, как сказано выше. Тогда (1, 1)-й элемент матрицы Ао равен с(о„ог). Д о к а з а т е л ь с т в о. А о — — ХА о, где Аьо 1„и Аз=Аз. ° А'о' для(~1. Индукцией по 1 легко показать, что (1, 1)-й элемент матрицы Аьо равен сумме стоимостей путей длины й, идущих из о, в оь Отсюда непосредственно следует, что (1, 1)-й элемент матрицы Ао равен сумме стоимостей всех путей нз о~ в оь П Из леммы 5,11 вытекает, что алгоритм 5.5 можно рассматривать как алгоритм вычисления замыкания матрицы. В теореме 5.5 утверждалось, что алгоритм 5.5 требует 0 (и') элементарньи операций в.е.
задачи о путях и вмножвнне мдтвип (т. е. операций +, ° и * над элементами полукольца). Обычный алгоритм умножения матриц также требует 0(п') элементарных операций. )т(ы покажем, что, когда элементы берутся из замкнутого полукольца, вычисление произведения двух матриц эквивалентно (по сложности) вычислению замыкания матрицы. Точнее, если дан какой-то алгоритм вычисления произведения матриц, то можно построить алгоритм вычисления замыкания, и обратно, причем порядок времени вычисления будет тем же. Значение этого результата лучше прояснится в гл. 6, где будет показано, что, когда элементы берутся из кольца, для умножения матриц хватает менее чем 0(п') операций.
Рассматриваемая конструкция состоит из двух частей. Теорема 5.6. Если замьлсание произвольной (п)(и)-матрицы над замкнутым полукольцом можно вычислить за такое время Т (и), что Т(Зи)(27Т(п) '), то существует алгоритм умножения двух (ахи)-матриц А и В с временем работы М (и), удовлетворяющим неравенству М(п)(сТ(п) для некоторой постоянной с.
Д о к аз а тел ь от в о. Пусть надо вычислить произведение А В двух (и)(и)-матриц А и В. Сначала образуем (Зих Зи)-матрицу Х= ООВ и найдем ее замыкание. Заметим, что Ха= ОО 0 и Х'=Х'=...= ООО Следовательно, 1„А А В Х'=)ев+Х+Х'= 0 )„В 00 l„ Так как А В можно прочитать в правом верхнем углу, заключаем отсюда, что М (п)(Т(Зп) =2ТТ(п). С) Это доказательство теоремы 5.6 имеет следующую интерпретацию в виде графа. Рассмотрим граф 0 с Зи узлами (1 ° 2,..., Зп).
Разобьем их на три множества У, (1, 2,..., и), У,=(и+1, п+2, ..., 2и) и У, (2п+1, 2п+2, ..., Зп). Будем считать, что все ребра графа 0 идут либо из Ут в У„либо из У, в У,. Такой граф ') Это допущение правдоподобно, поскольку Т(п) есть 0(пе) в худшем слу. яае. На самом деле в теореме подойдет любая постоянная (а не только 27). гл. $.
АлГОРитмы ИА ГРАФАХ а+! 2«+ 3 Рис. 6.2!. Ивтерпретвпия теоремы 6.6 в виде графа. изображен на рис. 6.21. Пусть А и  — такие (пхп)-матрицы, что (1, 1)-й элемент матрицы А служит меткой ребра, идущего из 1 в и+1, а (г, 1)-й элемент матрицы В служит меткой ребра, идущего из п+! в 2«+1. Тогда (1, !)-й элемент произведения А ° В оказывается суммой меток путей, идущих из ( в 2п+1, поскольку каждый такой путь образован ребром из 1 в некоторый узел й, п(й(2п, н следующим за иим ребром из й в 2«+1. Поэтому сумма меток всех путей из 1 в 2п+! совпадает с (1, 1)-м элементом матрицы А В.
Теперь докажем обращение теоремы 6.6. По данному алгоритму умножения матриц можно найти алгоритм замыкания, время работы которого с точностью до постоянного множителя совпадает с временем работы данного алгоритма. Теорема 6.7. Если произведение любых двух (пх п)-матриц над замкнутым полукольцом можно вычислить за такое время М (и), что М (2п)'= 4М (и), то существует алгорипии, вычисляющий замыкание матрицы за время Т(п), удовле«1воряюи(ее неравенству Т(п)(сМ (и) для некоторой постоянной с. Д о к а з а т е л ь с т в о.
Пусть Х вЂ” (п хи)-матрица. Сначала рассмотрим случай, когда и — степень числа 2, скажем 2'. Разобьем Х на четыре матрицы размера 2" 'х2»»! В силу леммы 6.11 можно считать, что матрица Х представляет граф 6= (У, Е), в котором множество узлов разбито на два множества У, и У, размера 2"-'. Матрица А представляет ребра между узлами мйожества У„матрица (1 — ребра между узлами из У„матрица В— ребра, идущие из узлов множества У, в узлы множества У„а мат- ав.
задачи о путях н имножинив матинц Рис. 5.22. Граф О. рица С вЂ” ребра, идущие из узлов множества У, в узлы множества У,. Это отражено на рис, 5.22, Путь из о, в ою концы которого принадлежат Уь либо 1) никогда не выходит за пределы У„либо 2) для некоторого й)1 найдутся такие узлы эн хь у, и ао где 1е~1~й, что все пч их~ лежат в У„всех, ну~ — в У., а рассматриваемый путь идет из о, в в, внутри У„затем по некоторому ребру уходит в х„потом вдоль некоторого пути внутри У, идет в узел у„ после чего по некоторому ребру уходит в ао затем по пути внутри У, идет в вв и т.
д. и, наконец, приходит в гв, откуда вдоль пути внутри У, идет в о,. Этот тип пути показан на рис. 5.23. Сумма меток, приписанных путям, удовлетворяющим условию 1 или 2, очевидно, равна (А+В 0е С)*. А именно, В Ре С представляет пути, идущие из щ в хь затем в р~ и далее в г~ на рис, 5.23. Рис. 5.23. Пути, удовлетворяявиие условию 2. 333 Гл.
а АлГОРитмы ИА ГРАФАХ ~Е Е.В.О» (Е Е~ 1 0'С Е 0'+Р' С.Е-В 0') ~,6 Н)' Матрицы Е, Е, 6 и Н можно вычислить, проделав такую последо- вательность шагов: Т, =0', Т,-В.ТИ Е=(А+Т, С)', Р=Е Т„ Т,=Т, С, Р= Тз'Е Н=Т,+Р Т,. Эти шаги требуют выполнения двух замыканий, шести умножений н двух сложений (2»-'х2»-')-матриц. Поэтому можно записать: Т(1) =1, Т(2»)а 2Т(2» ')+6М(2» ')+2 2'" ', й>1.
Три слагаемых в правой части неравенства (5.6) — это сложности соответственно замыканий, умножений и сложений. Мы утверждаем, что найдутся такие постоянная с н функция Т, что Т(2»)( (сМ(2») и Т удовлетворяет (5.6) для всех й. Базис, т. е. случай я=О, тривиален, поскольку постоянную с можно взять сколь угодно большой. Для проведения шага индукции предположим, что Т(2»-1)~ (сМ (2»-') для некоторой постоянной с. Из условия теоремы, т. е.
нз неравенства М(2п)~4М(а), заключаем, что М(2»-'))2'»-', (Заметим, что М (1)=1.) Следовательно, из (5.6) вытекает, что Т(2») ((2с-1-8) М(2» '). Снова в силу условия теоремы М(2»-')(",,М(2»), так что Т (2") ( ( — с+ 2 ) М (2"). (5.7) хза Следовательно, А+В О* ° С представляет те пути, соединяющие узлы в У„которые либо состоят из одного ребра, либо прыгают прямо в Ум остаются там на некоторое время и затем прыгают обратно в У,. Все пути, соединяющие узлы из множества Уо можно представить в виде последовательности путей, представленных матрицей А+В ° 0* ° С. Таким образом, (А+В Р* ° С)» представляет все пути, соединяющие узлы из У,.
Следовательно, верхний левый угол матрицы Х» занят матрицей (А+В 0» ° С)». Обозначим (А+В Р' С)» через Е. С помощью аналогичных рассуждений можно представить матрицу Х" в виде 6.Ю. ЗАДАЧИ С ОДНИМ ИСТОЧНИКОМ Если взять с- 4, то (5.7) влечет за собой Т(2А) сМ(2"), а это и требовалось доказать.
Если и не является степенью числа 2, то можно вложить Х в ббльшую матрицу, размер которой есть степень числа 2: (х х1 где 1 — единичная матрица минимально возможного размера. Это вложение увеличит размер матрицы не более чем вдвое, и, значит, постоянная увеличится не более чем в 8 раз. Таким образом, найдется такая постоянная с', что Т(п) =с'М (и) для всех п независимо от того, являются ли они степенями числа 2 илн нет.
П Следствие Е Время, необходимое для вычисления замыкания булевой матрицы, имеет тот же порядок, что и время вычисления произведения двух булевых м триц того же размера. В гл. 5 мы познакомимся с асимптотически более быстрыми алгоритмамн вычисления произведения булевых матриц и тем самым покажем, что транзитивное замыкание графа можно вычислить за время, меньшее 0(п'). Следствие 2. Время, необходимое для вычисления замыкания матрицы над множеством неотрицательных целых чисел с операциями М11Ч и + в качестве сложения и умножения элементов, имеет тот же порядок, ипо и время вычисления произведения двух матриц таково же типа. В настоящее время все известные методы решения задачи о нахождении кратчайших путей для всех пар узлов тратят не меньше сп' времени для некоторой постоянной с.
5ЛО. ЗАДАЧИ С ОДНИМ ИСТОЧНИКОМ Во многих приложениях достаточно находить кратчайшие пути только из одного узла (источника). На самом деле нам, быть может, надо найти кратчайший путь между двумя конкретными узлами, однако неизвестен алгоритм, который решал бы эту задачу эффективнее (в худшем случае), чем лучший из известных алгоритмов для одного источника. Для задач с одним источником мы не знаем объединяющего понятия, аналогичного замкнутым полукольцам и алгоритму 5.5. Если мы хотим только узнать, к каким узлам идут пути из источника, то задача тривиальна и ее можно решить несколькими алгоритмами, работающими 0(е) времени на е-реберном графе.
Так как алгоритм, если не "просматривает" все ребра, не может быть ГЛ. а АЛГОРИТМЫ НА ГРАФАХ 1 б(п !. 5 — (о,»; 2. Р[о,] — 0'1 3. 1ог оЕУ вЂ” (о,» бо Р[и] 1(о„о)1 4. в(т(1е 3~1/ бо Ьед(п б. выбрать узел вЕУ вЂ” Я, для которого Р[в] принимает наименьшее значение; б. добавить в к 3; 1 бР— В до 8.
Р[и] - М1И(Р[и], Р[в]+ 1(в, о)) епб епб Рис. б.яч, Алгоритм дсакстры. корректным, нетрудно убедиться, что время 0(е) наилучшее, на что можно надеяться. В задаче нахождения кратчайших путей из одного источника ситуация иная. Хотя иет причин предполагать, что для ее решения понадобится более 0(е) времени, ни один такой алгоритм не известен. Мы обсудим алгоритм сложности 0(п'), работа которого основана на построении множества 5 узлов, кратчайшие расстояния до которых от источника известны.
На каждом шаге к Я добавляется тот из оставшихся узлов, скажем о, расстояние до которого от источника меньше всех других оставшихся узлов. Если стоимости всех ребер неотрицательны, то можно быть уверенным, что путь из источника в о проходит только через узлы из Я. Поэтому достаточно найти для каждого узла о кратчайшее расстояние до него от источника вдоль пути, проходящего только через узлы из 5, Изложим алгоритм формально.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
