Главная Промышленная автоматика.

оно есть, и + с» в противном случае. Затем заменим строку 5 оператором (5.5), и по теореме 5.5 значение с {vt, vj), выданное алгоритмом 5.5, будет наименьшей стоимостью (т. е. суммой стоимостей ребер) пути из всех путей между Vi и vj.

Пример 5.13. Рассмотрим опять граф на рис. 5.18. Пусть каждое ребро помечено, как указано на рисунке. Тогда функции /, Q/, С}/, (Уц и Qj примут значения, как в таблицах на рис. 5.20. Например, С?а=МШ(С„ С?2+Са)=МШ (8, 5+2)=7. □

5.9. ЗАДАЧИ О ПУТЯХ И УМНОЖЕНИЕ МАТРИЦ

Пусть (S, +, •, О, 1) - замкнутое полукольцо. Можно определить (п X п)-матрицы элементов из S с обычными суммой и произведением. Иными словами, пусть матрицы А, В и С состоят из элементов Oi], blj и Cij соответственно для lt, }п. Тогда С=А-\-В означает, что Cij=atj+bij для всех i и /, а С=Л -В означает, что

Cij=ikbkj для всех i и /. Легко доказать следующую лемму.

Лемма 5.10. Пусть (S, -f, •, О, 1) - замкнутое полукольцо и Мп - множество (пХп)-матриц над S. Пусть -f„ и •„ обозначают соответственно сложение и умножение матриц, 0„ - матрица, все элементы которой равны О, а /„ - матрица с 1 на главной диагонали и О вне ее. Тогда (М„, +п, п. Оц. Ю - замкнутое полукольцо.

Доказательство. Оставляем в качестве упражнения. □

Пусть G= (У, Е) - ориентированный граф, где V={Wi, «г, . . ., и„}. Пусть функция разметки /: {VxV)~ S определена, как в алгоритме 5.5, а Aq обозначает (пХп)-матрицу с aij==l{Vi, Vj). Следующая лемма связывает вычисление, выполняемое алгоритмом 5.5, с вычислением замыкания Aq матрицы А в полукольце М„ (пХп)-матриц над S.

Лемма 5.11. Пусть G и Aq пшковы, как сказано выше. Тогда (i, j)-u элемент матрицы Aq равен c{Vi, Vj).

Доказательство. Л*о=Л, где Л/п и Aa=AQ-

• Ао для»>1. Индукцией по i легко показать, что (i, у)-й элемент матрицы А равен сумщ стоимостей путей длины k, идущих из Vi в Vj. Отсюда непосредственно следует, что (i, /)-й элемент матрицы Аа равен сумме стоимостей всех путей из у,- в vj. □

Из леммы 5.11 вытекает, что алгоритм 5.5 можно рассматривать как алгоритм вычисления замыкания матрицы. В теореме 5.5 утверждалось, что алгоритм 5.5 требует О (л*) элементарных операций



5.9. ЗАДАЧИ О ПУТЯХ И УМНОЖЕНИЕ МАТРИЦ

(т. е. операций +, • и * над элементами полукольца). Обычный алгоритм умножения матриц также требует О(п) элементарных операций. Мы покажем, что, когда элементы берутся из замкнутого полукольца, вычисление произведения двух матриц эквивалентно (по сложности) вычислению замыкания матрицы. Точнее, если дан какой-то алгоритм вычисления произведения матриц, то можно построить алгоритм вычисления замыкания, и обратно, причем порядок времени вычисления будет тем же. Значение этого результата лучше прояснится в гл. 6, где будет показано, что, когда элементы берутся из кольца, для умножения матриц хватает менее чем О (л) операций. Рассматриваемая конструкция состоит из двух частей.

Теорема 5.6. Если замьитние произвольной (пХп)-матрицы над замкнутым полукольцом можно вычислить за такое время Т(п), что Т {Зп)27Т (п) *), то существует алгоритм умножения двух (пХп)-матриц А и В с временем работы М(п), удовлетворяющим неравенству М{п)сТ{п) для некоторой постоянной с.

Доказательство. Пусть надо вычислить произведение А -В двух (пХп)-матриц А и В. Сначала образуем (Зп X Зп)-матрицу

/О А 0\

Х=1 О О В

\0 О О/

и найдем ее замыкание. Заметим, что О О А-В

О ] и Х»=Х* = О



Следовательно,


Так как А -В можно прочитать в правом верхнем углу, заключаем сугсюда, что М (пХГ(Зп)<27Г(п). □

Это доказательство теоремы 5.6 имеет следующую интерпретацию в виде графа. Рассмотрим граф G с Зп узлами {1, 2, . . ., Зп}. Разобьем их на три множества Vi={l, 2, . . ., п}, У2={«+1. п+2, . . ., 2п} и V8={2ft+1, 2п+2, . . ., Зп}. Будем считать, что все ребра графа G идут либо из Vt в Уг, либо из Va в Vs. Такой граф

1) Это допущение правдоподобно, поскольку Г (я) есть О (я) в худшем случае. На самом деле в теореме подойдет любая постоянная (а не только 27).




2/2+3

Рис. 5.21. Интерпретация теоремы 5.6 в виде графа.

изображен на рис. 5.21. Пусть А н В - такие (п X п)-матрицы, что (/, /)-й элемент матрицы А служит меткой ребра, идущего из i в n+j, а (t, /)-й элемент матрицы В служит меткой ребра, идущего из n+i в 2п+}. Тогда (t, /)-й элемент произведения АВ оказывается суммой меток путей, идущих из i в 2п+}, поскольку каждый такой путь образован ребром из ( в некоторый узел k, n<.k2n, и следующим за ним ребром из k в 2n+j. Поэтому сумма меток всех путей из i в 2n+j совпадает с (I, /)-м элементом матрицы А -В.

Теперь докажем обращение теоремы 5.6. По данному алгоритму умножения матриц можно найти алгоритм замыкания, время работы которого с точностью до постоянного множителя совпадает с временем работы данного алгоритма.

Теорема 5.7. Если произведение любых двух (пХп)-матриц над замкнутым полукольцом можно вычислить за такое время М(п), что iW (2л)>4Л1 (п), то существует алгоритм, вычисляюш,ий замыкание мсиприцы за время Т{п), удовлетворяющее неравенству Т {п)сМ (п) для некоторой постоянной с.

Доказательство. Пусть X -(пхп)-матрица. Сначала рассмотрим случай, когда п - степень числа 2, скажем 2*. Разобьем X на четыре матрицы размера 2*-ix2*-i:

{с о)

В силу леммы 5.11 можно считать, что матрица X представляет граф G= {V, Е), в котором множество узлов разбито на два множества и Va размера 2*~. Матрица А представляет ребра между узлами множества Vl, матрица D - ребра между узлами из Vi, матрица В - ребра, идущие из узлов множества Vi в узлы множества Vg, а мат-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 [73] 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0024