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

(S.-f, •, О, 1), где S - множество элементов, а + и • - бинарные операции на S, обладающие следующими пятью свойствами:

1) (S, +, 0) - моноид, т. е. множество S замкнуто относительно + {a-\-bS для всех а и b из S), операция -f ассоциативна (а4- (Ь+с)= (а4-Ь)+с для всех а, Ь, с из S) и О служит единичным элементом (а+0=0+а=а для всех а из S). Тройка (S, •, 1) также является моноидом. Кроме того, мы предполагаем, что О служит аннулятором, т. е. д. 0=0-0=0.

2) Операция + коммутативна (a+b=b-\-ay и идемпотентна (а-\-а=а).

3) Операция • дистрибутивна относительно + (а • (Ь -Ь с)=а • b + + а • с и (Ь+с) •а=Ь- а+с • а):

4) Если а±, Оа, . . ., flj, . . . - счетная последовательность элементов из S, то сумма fli-faa-f. . .+аг+. . . существует и единственна. Более того, ассоциативность, коммутативность и идемпотентность выполняются не только для конечных, но и для бесконечных сумм.

5) Операция • дистрибутивна не только относительно конечных сумм, но и относительно счетных (это не следует из свойства 3). Таким образом, из свойств 4 и 5 вытекает, что

(2a,)-(y) = 2(«,-)=S(S(«,-V)-

пример 5.9. Приведем три системы замкнутых полуколец. 1. Пусть Si=({0, 1), +, •, О, 1), а сложение и умножение заданы таблицами

Свойства 1-3 проверить легко. Что касается свойств 4 и 5, то заметим, что счетная сумма равна О тогда и только тогда, когда все слагаемые равны 0.

2. Пусть Si={R, MIN, +, +00, 0), где R - множество неотрицательных вещественных чисел, включая -f-cx). Легко проверить, что -foo служит единичным элементом для MIN, а О - для +.

3. Пусть S - конечный алфавит (т. е. множество символов) и 8з= (f Z, и , •, 0, {е}), где f i - семейство множеств, состоящих из конечных цепочек символов из Е, включая пустую цепочку в (т. е. цепочку длины 0). Здесь U обозначает операцию объединения



5.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ

множеств, а • - их конкатенацию Единичным элементом для и служит 0, а для • - {в}. Свойства 1-3 читатель может проверить сам. Что касается свойств 4 и 5, то достаточно заметить, что счетные объединения определяются такой эквивалентностью: (AiU UaU- • •) равносильно xAt для некоторого i. □

Центральной операцией в нашем анализе замкнутых полуколец будет унарная операция *, называемая замыканием. Если (S, +, •,

о, 1) - замкнутое полукольцо и agS, то положим а*-Уа, где

ао=1 и а=а-а-. Иными словами, значение а* равно бесконечной сумме 1+а+а-а+аа-а+. . . . Заметим, что свойство 4 определения замкнутого полукольца гарантирует, что а* б S. Из свойств 4 и 5 вытекает равенство а* = 1+аа*. Отметим, что 0* = 1* = 1.

Пример 5.10. Рассмотрим полукольца Si, Sa и Ss из примера 5.9. В Si выполняется а* = 1 для а=0 или 1. В Sa равенство а*=0 выполнено для всех а £ 7?. В Ss выполняется Л* = {е} и {Лха- • • А>1 а XtA для 1<1<й} для всех AF,. Например, {а, Ь}* = = {е, а, Ь, аа, аЬ, Ьа, bb, ааа, . . .}, т. е. {а, Ь}* состоит из всех цепочек символов а и Ь, включая пустую цепочку. Вообще Fx= =5(2*), где SiX) обозначает множество-степень для X. □

Теперь возьмем ориентированный граф G= {V, Е), в котором каждое ребро помечено элементом некоторого замкнутого полукольца (S, +, •, О, 1) ). Определим метку пути как произведение (•) меток ребер, составляющих этот путь, причем метки берутся в порядке прохождения ребер. В частности, метка пути нулевой длины равна 1 (единичному элементу для операции • рассматриваемого полукольца). Для каждой пары узлов (v, w) определим с (и, w) как сумму меток всех путей между v к w. Назовем с (и, w) стоимостью прохождения т v в w. Условимся считать, что сумма по пустому множеству путей равна О (единичному элементу для операции + нашего полукольца). Заметим, что если G имеет циклы, то между V и W может быть бесконечно много путей, но аксиомы замкнутого полукольца гарантируют, что c(v, w) определяется корректно.

Пример 5.11. Рассмотрим ориентированный граф на рис. 5.17,

в котором каждое ребро помечено элементом полукольца Si, описанного в примере 5.9. Метка пути v, w, х равна 1 • 1 = 1. Простой

1) Конкатенацией А-В множеств А и В называется множество {х\х=уг. уА и гВ).

2) Читателю следует не упустить из виду аналогию между рассматриваемой ситуацией и недетерминированным конечным автоматом (см. Хопкрофт, Ульман [1969] или Ахо, Ульман [1972]), который мы еще обсудим в разд. 9.1. Там узлы представляют собой состояния, а метки ребер - символы из некоторого конечного алфавита.



Рис. 5.17. Помеченный ориентированный граф.

ЦИКЛ КЗ W в W имеет метку 1 • 0=0. Вообще каждый путь положительной длины, идущий из W BW, имеет метку 0. Однако стоимость пути нулевой длины из ш в ау равна 1. Следовательно, c(w, w)=l □

Изложим алгоритм вычисления c{v, w) для всех пар узлов v uw. Основными шагами этого алгоритма, занимающими единицу времени, будут операции +, - и * произвольного замкнутого полукольца. Конечно, для таких структур, как множество всех множеств цепочек над некоторым алфавитом, не понятно, можно ли в принципе реализовать эти операции в отведенное им "единичное время". Но для тех полуколец, которыми мы будем пользоваться, эти операции легко выполнимы.

Алгоритм 5.5. Вычисление стоимости прохождения между узлами

Вход. Ориентированный граф G= (V, Е), где V={vi, v, . . ., Vn) и функция разметки /: (УХ S, где (S, +, •, О, 1) - замкнутое полукольцо. Полагаем l{Vi, t))=0, если (vt, V])E.

Выход. Для всех i и /, заключенных между 1 и п, элемент с (к,, Vj) из S, равный сумме по всем путям из Vi в Vj меток этих путей.

Метод. Вычисляем С/ для всех l<t<n, 1</<п и 0<Л<п. Величины Cij задуманы как суммы меток путей, идущих из у,- в Vj, все узлы которых, кроме, быть может, концов, принадлежат множеству {Vi, Vi, . . ; t)ft}. Например, путь у„, «з, Vg рассматривается при вычислении Cg и Clg, но не Clg. Алгоритм выглядит так:

begin

1. for t 1 until п do С], 1 +l{Vi, V,);

2. for l<i, /<п и do C4i*-l{Vi, Vj);

3. for k*-\ until n do

4. for 1 < t, / < rt do

5. cli or+c?*- • (Cfe) * • Cif,

6. for 1 < /, / < rt do с (v,, V,) CI

end □

Теорема 5.5. Алгоритм 5.5 использует O(n) операций +, • ы * из полукольца и вычисляет с {vt, Vj) для l<t, jn.

Доказательство. Легко проверить, что строка 5 выполняется л* раз, причем каждый раз используются четыре операции, и for-циклы в строках 1, 2 и 6 итерируются не более раз каждый. Поэтому достаточно О (л*) операций.





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