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

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


Рис. 5.22. Граф О.

рица С - ребра, идущие из узлов множества V, в узлы множества Vl. Это отражено на рис. 5.22.

Путь из Vl в 2. концы которого принадлежат Vi, либо

1) никогда не выходит за пределы Vi, либо

2) для некоторого kl найдутся такие узлы Wt, Xi, yi и 2j, где

что все Wi и Zj лежат в Vi, все Xt к yt - в Va, а рассматриваемый путь идет из Vi в Wi внутри Vi, затем по некоторому ребру уходит в Хи потом вдоль некоторого пути внутри Va идет в узел уи после чего по некоторому ребру уходит в Zi, затем по пути внутри Vi идет в аУа и т. д. и, наконец, приходит в Zj, откуда вдоль пути внутри Vi идет в t>a. Этот тип пути показан на рис. 5.23.

Сумма меток, приписанных путям, удовлетворяющим условию 1 или 2, очевидно, равна {A+B-D* -С)*. А именно, B-D*-С представляет пути, идущие из аУ в xt, затем в и далее в Zj на рис. 5.23.


Рис. 5.23. Пути, удовлетворяющие условию 2.



Следовательно, A+B-D* - С представляет те пути, соединяющие узлы в Vl, которые либо состоят из одного ребра, либо прыгают прямо в Vl, остаются там на некоторое время и затем прыгают обратно в Vl. Все пути, соединяющие узлы из множества Vi, можно представить в виде последовательности путей, представленных матрицей A+B-D* -С. Таким образом, (Л+В** «С)* представляет все пути, соединяющие узлы из Vi. Следовательно, верхний левый угол матрицы X* занят матрицей {A+B-D* -С)*.

Обозначим (A+B-D* - С)* через Е. С помощью аналогичных рассуждений можно представить матрицу X* в виде

ГЕ E-B.D* \-f

*~\D*-C-E D* + D*-CE-B-D\I~\G Н

Матрицы Е, F, G и Н можно вычислить, проделав такую последовательность шагов:

Ti=D*, T.-B-Ti,

E = (A + Ti.C)\

F = E-T„ Ts = Ti-C,

G = T,-E,

H=Ti + G-T2.

Эти шаги требуют выполнения двух замыканий, шести умножений и двух сложений (2*-1х2*~1)-матриц. Поэтому можно записать:

r(2*)<2r(2*-i) + 6M(2*-i)-f 2-2»*-«, k>\.

Три слагаемых в правой части неравенства (5.6) - это сложности соответственно замыканий, умножений и сложений. Мы утверждаем, что найдутся такие постоянная с и функция Т, что Г (2*): <сМ (2*) и Т удовлетворяет (5.6) для всех k. Базис, т. е. случай /г=0, тривиален, поскольку постоянную с можно взять сколь угодно большой. Для проведения шага индукции предположим, что 7(2*-iX cM(2*~i) для некоторой постоянной с. Из условия теоремы, т. е. из неравенства М (2п)Ш (п), заключаем, что М (2*-i)>2"=-*. (Заметим, что Л1(1)=1.) Следовательно, из (5.6) вытекает, что

Т (2*) < (2с+ 8) М (2*-1). Снова в силу условия теоремы М (2-)/М (2), так что

Г(2*)<(1с+2)М(2*). (5.7)



Если взять (4, то (5.7) влечет за собой Г (2*ХсМ (2*), а это и требовалось доказать.

Если п не является степенью числа 2, то можно вложить X в большую матрицу, размер которой есть степень числа 2:

где / - единичная матрица минимально возможного размера. Это вложение увеличит размер матрицы не более чем вдвое, и, значит, постоянная увеличится не более чем в 8 раз. Таким образом, найдется такая постоянная с, что Т {п)сМ (п) для всех п независимо от того, являются ли они степенями числа 2 или нет. □

Следствие 1. Время, необходимое для вычисления замыкания булевой матрицы, имеет тот же порядок, что и время вычисления произведения двух булевых матриц того оке размера.

В гл. 6 мы познакомимся с асимптотически более быстрыми алгоритмами вычисления произведения булевых матриц и тем самым покажем, что транзитивное замыкание графа можно вычислить за время, меньшее О (л).

Следствие 2. Время, необходимое для вычисления замыкания матрицы над множеством неотрицательных целых чисел с операциями MIN « + б качестве сложения и умножения элементов, имеет тот же порядок, что и время вычисления произведения двух матриц такого же типа.

В настоящее время все известные методы решения задачи о нахождении кратчайших путей для всех пар узлов тратят не меньше сп времени для некоторой постоянной с.

5.10. ЗАДАЧИ С ОДНИМ ИСТОЧНИКОМ

Во многих приложениях достаточно находить кратчайшие пути только из одного узла (источника). На самом деле нам, быть может, надо найти кратчайший путь между двумя конкретными узлами, однако неизвестен алгоритм, который решал бы эту задачу эффективнее (в худшем случае), чем лучший из известных алгоритмов для одного источника.

Для задач с одним источником мы не знаем объединяющего понятия, аналогичного замкнутым полукольцам и алгоритму 5.5. Если мы хотим только узнать, к каким узлам идут пути из источника, то задача тривиальна и ее можно решить несколькими алгоритмами, работающими 0{е) времени на е-реберном графе. Так как алгоритм, если не "просматривает" все ребра, не может быть





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.1023