1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 45
Текст из файла (страница 45)
Пусть 5,=(Н, М15), +, +Фа„О), где )т — множество неотрицательных вещественных чисел, включая +со. Легко проверить, что +со служит единичным элементом для М1!ч, а 0 — для +. 3. Пусть л. — конечный алфавит (т. е. множество символов) и 5э=(рх 11, ', 8, (е)), где Гх — семейство множеств, состоящих из конечных цепочек символов нз А:, включая пустую цепочку з (т. е.
цепочку длины 0). Здесь 0 обозначает операцию объединения Пример 5.9. Приведем три системы замкнутых полуколец. 1. Пусть 5,= ((О, 1), +,, О, 1), а сложение и умножение заданы таблицами 6.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ множеств, а ° — их конкатенацию '). Единичным элементом для [) служит Я, а для ° — (е). Свойства 1 — 3 читатель может проверить сам, Что касается свойств 4 и 5, то достаточно заметить, что счетные объединения определяются такой эквивалентностью: хЕ (А, О [)Ае[)...) равносильно хЕАг для некоторого й [ [ Центральной операцией в нашем анализе замкнутых полуколец будет унарная операция *, называемая замыкаиием.
Если (Я, +, Ф О, 1) — замкнутое полукольцо и а [~ Я, то положим ае=Дгг, где а'=1 и а'=а а'-'. Иными словами, значение ае равно бесконечной сумме 1+а+а.а+а.а а+.... Заметим, что свойство 4 опреде. ления замкнутого полукольца гарантирует, что а* ЕЗ. Из свойств 4 и 5 вытекает равенство ив=1+а а*. Отметим, что 0*=-1*=1. Пример 5.10. Рассмотрим полукольца 5„5з и Яе из примера 5.9. В Яг выполняется а*=1 для а=О илн 1. В 5, равенство а*=О выполнено для всех а Е гс. В Зз выполняется А * = (е) [) (х,х,... ха[ й)1 и хг ЕА для 1(г(й) для всех А Е ге.
Например, (а, Ь)"= =(е, а, Ь, аа, аЬ, Ьа, ЬЬ, ааа,...), т. е. (а, Ь)* состоит из всех цепочек символов а и Ь, включая пустую цепочку. Вообще г"е= =э" (г.е), где а'(Х) обозначает множество-степень для Х. С) Теперь возьмем ориентированный граф 0= (У, Е), в котором каждое ребро помечено элементом некоторого замкнутого полукольца (Я, +, , О, 1) '). Определим иениу праги как произведение ( ) меток ребер, составляющих этот путь, причем метки берутся в порядке прохождения ребер.
В частности, метка пути нулевой длины равна 1 (единичному элементу для операции рассматриваемого полукольца). Для каждой пары узлов (о, гн) определим с(о, ю) как сумму меток всех путей между о и гн. Назовем с(р, гн) стоимостью прохождения из о в гн. Условимся считать, что сумма по пустому множеству путей равна О (единичному элементу для операции + нашего полукольца). Заметим, что если б имеет циклы, то между р и гн может быть бесконечно много путей, но аксиомы замкнутого полукольца гарантируют, что с(р, гн) определяется корректно. Пример 5.11.
Рассмотрим ориентированный граф на рис. 5.17, в котором каждое ребро помечено элементом полукольца Я„ описанного в примере 5.9. Метка пути о, гн, х равна 1 ° 1 =1. Простой г) Конкппмианпей А В множеств А и В называется множество (х[х=уг уЕА и гЕВ). з) Читателю следует ие упустить из виду аналогию между рассматриваемой ситуацией и недетермииированиым конечным автоматом (см. Хопкрофг, Ульмаи [19991 илн Ахо, Ульман [19721), который мы еце обсудим в равд. 9.1.
Там узлы представляют собой состояния, а метки ребер — символы из некоторого конечного алфавита. ггэ В А. Ахо, Дж. Хопкрейт. Дж. Уаьмев ГЛ. а. АЛГОРИГМЫ НА ГРАФАХ Рнс. 5.17. Помеченный орнентнрованный граф. цикл из юо в юс имеет метку 1.О=О. Вообще каждый путь положительной длины, идущий из юо в юо, имеет метку О. Однако стоимость пути нулевой длины изиви1равна1.Следовательно, с(юо, ию)=1 П Изложим алгоритм вычисления с(о, ию) для всех пар узлов о и юо. Основными шагами этого алгоритма, занимающими единицу времени, будут операции +, и ' произвольного замкнутого полукольца.
Конечно, для таких структур, как множество всех множеств цепочек над некоторым алфавитом, не понятно, можно ли в принципе реализовать эти операции в отведенное им "единичное время". Но для тех полуколец, которыми мы будем пользоваться, эти операции легко выполнимы. Алгоритм 5.5. Вычисление стоимости прохождения между узлами Вход. Ориентированный граф б= (г', Е), где г'=(о„ ое, ..., о„) и функция разметки 1: (г'11'г') -1- 5, где (5, +, , О, 1) — замкнутое полукольцо. Полагаем 1(ою, ою)=0, если (ою, о,) ю/Е. Выход.
Для всех ю и 1, заключенных между 1 и и, элемент с(ою, ою) нз В, равный сумме по всем путям из ою в ою меток этих путей. Метод. Вычисляем Саюг для всех !<ю -и, 1<1<и и 0<И. и. Величины Са„задуманы как суммы меток путей, идущих из о, в оь все узлы которых, кроме, быть может, концов, принадлежат множеству (о„о„..., о„). Например, путь о„, о„о, рассматривается при вычислении С,', и С'„, но не С'„. Алгоритм выглядит так: Ьей(п 1. 1ог ю — 1 пп1П и до С',ю — 1+1(о„о,); 2, 1ог 1<ю', /<и и ю'Ф*/ до Сюю !(о,, ою); 3. 1ог й -1 пи(11 и до л 1ог 1 < 1, / < п до 5. СА СА 1 1 СА 1, (С$-1)е СА 1, 6. 1ог 1<1, /<п до с(о,,ою) -С"и епд П Теорема 5.6. Алгоритм 5.5 использует 0(п') операций +, ° и е из полукольца и вычисляет с(ою, ою) длл 1<1, 1<и.
Д о к а з а тел ь с т в о. Легко проверить, что строка 5 выполняется и' раз, причем каиюдый раз используются четыре операции, и 1ог-циклы в строках 1, 2 и 6 итерируются не более и' раз каждый. Поэтому достаточно 0(и') операций. З.т. АлГОРитм тРАнзиТиВНОГО зАмыкАния Чтобы доказать корректность, надо доказать индукцией по й, что С» — сумма меток всех путей нз и, в оь не содержащих промежуточных (т. е. отличных от концов) узлов с индексами, большими й. Базис, т.
е. случай А=0, тривиален в силу строк 1 и 2, поскольку любой такой путь имеет длину 0 илн состоит из единственного ребра. Шаг индукции получается на основании строки 5, ибо путь из пг в пь не содержащий промежуточных узлов с индексами, большими н, либо 1) не содержит промежуточных узлов с индексами, большими й — 1 (слагаемое С»)-'), либо 2) идет из о, в ам затем несколько раз (возможно, ни разу) из о» в и» и, наконец, из и в пь причем везде на этих участках нет промежуточных узлов с индексами, большими й — 1 (слагаемое С»г, ' ° 1С»ы')е С» »~г). Аксиомы замкнутого кольца гарантируют, что в строке 5 кор.
ректно вычисляется сумма меток всех этих путей. П 5.7. АЛГОРИТМ ТРАНЗИТИВНОГО ЗАМЫКАНИЯ Изучим алгоритм 5.5 для двух интересных случаев. Первый случай — замкнутое полукольцо 5„ описанное в примере 5.9. В 5, легко выполнить сложение и умножение, а также и операцию е, поскольку Ое=1е=1. Действительно, так как 1 служит единичным элементом относительно , строку 5 алгоритма 5.5 можно заменить на ') С' -С' '+С' ' С" '. И г/ М ' »1 (5.4) Чтобы вычислить рефлексивно-транзитнвное замыкание графа, зададим функцию разметки ! , если (и, гп) — ребро графа, 1(п, гп) = 0 в противном случае. Стоимость с(п, ш) равна 1 тогда и только тогда, когда нз и в ш идет путь длины 0 или больше.
Это легко проверить с помощью аксиом замкнутого полукольца (О, 1). Пример 5.12. Рассмотрим граф на рис. 5.18, временно игнорируя числа на ребрах. Функция разметки 1(пи и;) задается таблицей ') Естественно интерпретировать вто так: чдостаточно исследовать только пути беа циклов». Тем не менее заметим, что с оператором (5Л) вместо строки 5 алгоритм 5.5 будет вычислять суммы по множествам путей, включающим не только все пути без циклов, но н некоторые другие. ГЛ. 6. АЛГОРИТМЫ ИА ГРАФАХ Рас.
5.10. Граф. и, из из Строка 1 алгоритма 5.5 дает Си=С'„=С"„=1. Строка 2 дает Сап=!(01, и!) для 1~1, так что получаем для С,", таблицу Теперь полагаем я=! и выполняем цикл в строках 4 и 5, где вместо строки 5 стоит(5.4). Например, С(з=С~+Сззз С,"а=О+! ° 1=1, Таблицы значений Сп, С'„и С'„приведены на рис. 5.19. П и, из из из из из С!=С!!=с(и,, и) Рис.
В.!9. Зиачеааз ф. и, из из ! 1 из 1 1 изО 1 1 1 1 100 010 1 1 ! 110 011 из 1 1 1 из 6.6. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ 5.6. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ ив ив ив ив ив ив и, 0 8 5 ив 3 0 оо и, оо 2 0 и, 2 8 5 ив 3 оо оо и, оо 2 оо ! (ивр о!) и! ив ив и, 0 8 5 и, 3 0 8 ив оо 2 0 О 8 5 3 0 8 5 2 0 ив ив и, 0 7 5 и, 3 0 8 и, 5 2 0 Свв =с(ог, и~) Рнс, 5.20.
Вычнсленне кратчайшего путы. Для вычисления кратчайшего пути воспользуемся вторым замкнутым полукольцом из примера 5.9, а именно множеством неотрицательных вещественных чисел вместе с +со. Напомним, что адднтивной операцией является М1)Ч, а мультипликативной— сложение вещественных чисел. Иными словами, рассмотрим структуру ()е, М1Н, +, +оо, 0). В примере 5.10 отмечалось, что де=О для всех аЕ)е, так что снова можно обойтись без операции * в строке 5 алгоритма 5.5, заменив зту строку на С"; М)Н(С„', С '+С '). (5.5) Неформально можно сказать, что оператор (5.5) означает, что кратчайшим путем из ив в иь не проходящим через узлы, индексы которых больше й, будет более короткий из следующих двух путей: 1) кратчайшего пути, не проходящего через узлы, индексы которых больше А — 1, и 2) кратчайшего пути из ов в ов и затем в оь не проходящего через другие узлы, индексы которых больше А — 1.
Чтобы превратить алгоритм 5.5 в алгоритм нахождения кратчайшего пути, зададим !(ии иг) как стоимость ребра (ов, о!), если л. 6. Алгогнтмы НА ГРАФАХ оно есть, и + оь в противном случае. Затем заменим строку 5 оператором (5.5), и по теореме 5.5 значение с(оь ог), выданное алгоритмом 5.5, будет наименьшей стоимостью (т. е. суммой стоимостей ребер) пути нз всех путей между оь и ор Пример 5.13.
Рассмотрим опять граф на рис, 5.18. Пусть каждое ребро помечено, как указано на рисунке. Тогда функции 1, Щ, С',ь Сп и С'„примут значения, как в таблицах на рис. 5.20. Например, С",,=М1Н (С1м С,',+С'„) =М1Ы (8, 5+2) =7. П 5.9. ЗАДАЧИ О ПУТЯХ И УМНОЖЕНИЕ МАТРИЦ Пусть (В, +,, О, 1) — замкнутое полукольцо. Можно определить (и Х п)-матрицы элементов из В с обычными суммой и произведением. Иными словами, пусть матрицы А, В и С состоят из элементов агь Ьы и сы соответственно для 1(~, )(и. Тогда С=А+В означает, что см — — ам+Ьм для всех 1 и 1, а С=А В означает, что ь с» — — ~~ Ьь~ для всех 1 и 1.
Легко доказать следующую лемму. ь=! Лемма 5.10. Пусть (5, +,, О, 1) — замкнутое полукольцо и ̄— множество (их и)-матриц над 3. Пусть +„и;, обозначают соответственно сложение и умножение матриц, ΄— матрица, все элементы которой равны О, а 1„— матрица с 1 на главной диагонали и О вне ее. Тогда (М„, +„, „, 0„, 1„) — замкнутое полукольцо. Доказательство. Оставляем в качестве упражнения. П Пусть 6=(г", Е) — ориентированный граф, где У=(оь о„..., о„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
