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

Чтобы доказать корректность, надо доказать индукцией по к, что С?,- сумма меток всех путей из Vi в Vj, не содержащих промежуточных (т. е. отличных от концов) узлов с индексами, большими к. Базис, т. е. случай k=Q, тривиален в силу строк 1 и 2, поскольку любой такой путь имеет длину О или состоит из единственного ребра. Шаг индукции получается на основании строки 5, ибо путь из Vi в V}, не содержащий промежуточных узлов с индексами, большими к, либо

1) не содержит промежуточных узлов с индексами, большими к-1 (слагаемое Cj), либо

2) идет из Vi в о, затем несколько раз (возможно, ни разу) из в и, наконец, из в Vj, причем везде на этих участках нет промежуточных узлов с индексами, большими к-1 (слагаемое СЧ • (Cli)*-Clf).

Аксиомы замкнутого кольца гарантируют, что в строке 5 корректно вычисляется сумма меток всех этих путей. □

5.7. АЛГОРИТМ ТРАНЗИТИВНОГО ЗАМЫКАНИЯ

Изучим алгоритм 5.5 для двух интересных случаев. Первый случай - замкнутое полукольцо Si, описанное в примере 5.9. В Si легко выполнить сложение и умножение, а также и операцию *, поскольку 0* = 1* = 1. Действительно, так как 1 служит единичным элементом относительно •, строку 5 алгоритма 5.5 можно заменить на )

C4i*-C\r + Clu-aj\ (5.4)

Чтобы вычислить рефлексивно-транзитивное замыкание графа, зададим функцию разметки

( 1, если {v,w) - ребро графа, / (и, оу) = < .

( О в противном случае.

Стоимость с (и, w) равна 1 тогда и только тогда, когда из и в оу идет путь длины О или больше. Это легко проверить с помощью аксиом замкнутого полукольца {О, 1}.

Пример 5.12. Рассмотрим граф на рис. 5.18, временно игнорируя числа на ребрах. Функция разметки l{Vi, Vj) задается таблицей

1) Естественно интерпретировать это так: «достаточно исследовать только пути без циклов». Тем не менее заметим, что с оператором (5.4) вместо строки 5 алгоритм 5.5 будет вычислять суммы по множествам путей, включающим не только все пути без циклов, но и некоторые другие.

8* 227




Рис, 5.18. Граф.

Vl Vt V3

V2 V3

1 1 1 1 О О О 1 О

Строка 1 алгоритма 5.5 дает С?,=С§2=С5з=1. Строка 2 дает C1i=l(Vi, Vj) для 1ф1, так что получаем для Q таблицу

«1 «а V3

1 1 1 1 1 о О 1 I

Теперь полагаем fe=l и выполняем цикл в строках 4 и 5, где вместо строки 5 стоит (5.4). Например, Сз=Сз+С§1 •С?з=0+1 •! = !. Таблицы значений C\j, Ьц и С\, приведены на рис. 5.19. □

Vl Vt

V3 V3

1 1

1 1

1 1

1 1

0 1

1 1

C% = Сц

= C(0„ Vf)

Рис. 5.19. Значения С?/.



5.8. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

5.8. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

Для вычисления кратчайшего пути воспользуемся вторым замкнутым полукольцом из примера 5.9, а именно множеством неотрицательных вещественных чисел вместе с -f-cx). Напомним, что аддитивной операцией является MIN, а мультипликативной - сложение вещественных чисел. Иными словами, рассмотрим структуру {R, MIN, +, +00, 0). В примере 5.10 отмечалось, что а*=0 для всех aR, так что снова можно обойтись без операции * в строке 5 алгоритма 5.5, заменив эту строку на

Cff MIN (С?г\ Ск + Cif). (5.5)

Неформально можно сказать, что оператор (5.5) означает, что кратчайшим путем из Vi в V), не проходящим через узлы, индексы которых больше k, будет более короткий из следующих двух путей:

1) кратчайшего пути, не проходящего через узлы, индексы которых больше k-l, и

2) кратчайшего пути из t>j в и затем в vj, не проходящего через другие узлы, индексы которых больше k-1.

Чтобы превратить алгоритм 5.5 в алгоритм нахождения кратчайшего пути, зададим l(Vi, Vj) как стоимость ребра (vt, Vj), если

2 8 5

3 oo oo oo 2 c»

4Vi, Vj)

Vl V2 Vs

Vl Vi Vg

0 8 5

3 0 oo

oo 2 0

Vl Vi

Vl Vt

0 8

0 8

3 0

3 0

oo 2

5 2

с (Vi,

«/)

Рис. 5.20. Вычисление кратчайшего пути.





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