1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 50
Текст из файла (страница 50)
5.387 Указание: Рассмотрите работу алгоритма на графе с 5 узлами, стоимости ребер которого указаны на рис. 5.39. 5.25. Постройте алгоритм, который распознавал бы, есть ли в данном ориентированном графе, ребрам которого приписаны поло. жительные и отрицательные стоимости, цикл отрицательной стоимости. 5.26. Измените правило выбора узла гн в алгоритме на рис. 5.38 так, чтобы гарантировать оценку времени 0(п') в случае, когда ребрам приписаны произвольные стоимости. 5.27. Напишите алгоритм, который по данной (пмл)-матрице М положительных целых чисел строил бы последовательность смежных элементов, начинающуюся с М[п, 1) и оканчивающуюся М[1, п], так, чтобы минимизировать сумму абсолютных значений разностей между соседними элементами.
Два элемента М[1,11 и М[л, 1) считаются смезсными, если (а) (=й~-1 и 1=1 или (б) 1=А и 1=1~1. Например, для рис. 5.40 решением будет последовательность 7,5,8,7,9,6,12. 5.28, Алгоритм на рис. 5.24 для каждого и 6 'Г' вычисляет наименьшую стоимость пути среди всех путей из ое в о. Модифицируйте этот алгоритм так, чтобы он строил некоторый путь наименьшей стоимости для каждого узла о из Г'. 1 9 6 12 8 7 3 5 5 9 11 4 7 3 2 6 Рнс. ЬАО. Матраца положительных целых чисел, УПРАЖНЕНИЯ **5.29.
Напишите программу, реализующую доминаторный алгоритм из равд. 5.11. Проблемы для исследования 5.30. Для многих проблем, связанных с графами, поиск в глубину мог бы принести пользу. Одна из них касается я-связности. Неориеитированный граф называется Ьсвязным, если для каждой пары узлов о и и существуют такие Й путей между ними, что ии один узел (кроме о и го) ие входит более чем в один путь Таким образом, двусвязность означает 2-связность. Хопкрофт, Тарьян 11973б) построили алгоритм, отыскивающий 3-связные компоненты за линейное время. Естественно выдвинуть гипотезу, что для каждого я есть алгоритм, отыскивающий я-связные компоненты за линейное (по числу узлов и ребер) время.
Не сможете ли вы найти такой алгоритм? 5.31. Другой интересной проблемой, для решения которой, быть может, нужен поиск в глубину (а, быть может, и нет), является построение алгоритма, отыскивающего за линейное (по числу ребер) время осговное дерево наименьшей стоимости. 5,32. Заслуживает рассмотрения и задача нахождения кратчайшего пути нз одного источника, когда е(~'. Существует ли алгоритм, отыскивающий за время 0(е) хотя бы кратчайшее расстояние между двумя конкретными точкамиу Читателю было бы полезно ознакомиться с упр. 5.21 и 5.22, основанными на диссертации Джонсона [1973), а также с работой Спиры, Пана П973), в которой показано, что в общем случае для таких алгоритмов требуется пЧ4 сравнений, если алгоритмы используют только сравнения между суммами стоимостей ребер.
Вагнер П9741 применил технику сортировки вычерпыванием, чтобы получить алгоритм сложности 0(е) в случае, когда в качестве стоимостей ребер фигурируют малые целые числа. 5.33. Было показано (Керр (1972)), что если допускаются только операции М1М и +, то проблема нахождения кратчайших путей между всеми парами узлов требует йпв шагов, где й — некоторая положительная постоянная. Рабин усилил этот результат до пв76. Тем не менее может оказаться, что если допустить другие операции, то можно будет получить алгоритм, работающий менее 0(п') времени. Например, как мы увидим в следующей главе, можно построить транзитивное замыкание (или, что эквивалентно, перемножить две булевы матрицы) быстрее, чем за 0(п') шагов, если допустить операции, отличные от булевых.
ГЛ. Э. АЛГОРИТМЫ ИА ГРАФАХ Замечання пе янтературе Сведения по теории графов можно почерпнуть из кинг Бержа [1958[ и Харари [!969]. Алгоритм 5.1, строящий остовные деревья наименьшей стоимости, взят из работы Крускала [1956]. Прим [195?] указывает другой подход к этой задаче. Алгоритм, предложенный в упр.5.3, указал нам Спира.
Алгоритм, касающийся двусвяэности и использующий поиск в глубину, принадлежит Хопкрофту. Алгоритм ддя сильно связных компонент взят у Тарьяна [1972]. В литературе отражены многочисленные применения поиска в глубину ддя построения оптимальных или наилучших нз известных алгоритмов. Хопкрофг, Тарьян [1973а] дают линейную проверку планзрностн. В другой работе Хопкрофт, Тарьян [1973б) описывают линейный алгоритм нахождения 3- связных компонент. Тарьян [1973а) на основе той же идеи разработал наилучший из известных алгоритмов нахождения доминаторов.
Кроме того, Тарьян [19736] предлагает тест для «речуцнруемости потоковых графов». Алгоритм 5.5, т. е. общий алгоритм нахождения путей, по существу, принадлежит Клнни [!956], который испольэовал его в связи с чрегулярнымн выражениями» (равд. 9.!). Данная здесь форма этого алгоритма заимствована у МакНотонз, Ямалы [1960]. Алгоритм сложности 0(пз), строящий транэнтнвное замыкание, взят из работы Уоршола [1962]. Аналогичный алгоритм, отыскивающий кратчайшие путы для всех пар узлов, заимствовав у Флойда [!962] (см. также Ху [!968]). Алгоритм для случая одного источняка изложен по работе Дейкстры [!959]. Спнра, Пан [1973] показышгют, что алгоритм Дейкстры, по существу, оптимален, если в качестве модели брать деревья решений. Данциг, Блаттиер, Рао [1967] заметнлн„что наличие ребер с отрицзтельиымн стоимостями не влияет на решение задачи нахождения кратчайших путей между всемя парами точек, если нет цикла с отрицательной стоимостью.
Джонсон [1973] обсуждает задачи с одним источником при наличии ребер с отрицательными стоимостями; он же приводит решения упр. 5.2! и 5.22. Спира [1973) дает алгоритм нахождения кратчайшего пути за среднее время 0(пз )ой» л). Связь между задачей нахождения путей и умножением матриц описана в работах Мунро [!97Ц н Фурмана [1970] (теорема 5.7) и Фишера, Мейера [197Ц (теорема 5.6). Связь с транзитивной редукцией (упр. 5.13 — 5.15) заимствована у Ахо, Гарн, Ульмана [1972[. Ивен [!973[ обсуждает Л-связность графов. УМНОЖЕНИЕ МАТРИЦ 6 И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ В этой главе мы исследуем асимптотическую вычислительную сложность умножения матриц, элементы которых берутся из произвольного кольца Мы увидим, что "обычный" алгоритм умножения матриц, имеющий сложность 0 (а'), можно асимптотически улучшить; чтобы умножить две (пХи)-матрицы, достаточно времени 0(п' "). Более того, мы увидим, что и другие операции, такие, как НВП-разложение, обращение матрицы и вычисление определителя, сводятся к умножению матриц, и потому их можно выполнить столь же быстро, как и умножение матриц.
Затем покажем, что умножение матриц сводится к обращению матрицы, и потому любое улучшение асимптотического времени решения одной из этих задач привело бы к аналогичному улучшению для другой. Закончим главу двумя алгоритмами умножения булевых матриц, асимптотическая временная сложность которых меньше 0(п'). По существу к алгоритмам этой главы не следует относиться как к практическим, если исходить из технических возможностей современных вычислительных машин. Одна из причин состоит в том, что из-за скрытых постоянных множителей они работают быстрее обычных алгоритмов сложности 0(а') только для достаточно больших значений и.
Кроме того, для этого семейства алгоритмов недостаточно хорошо понято поведение ошибок округления. Тем не менее идеи данной главы, на наш взгляд, заслуживают рассмотрения, поскольку оии свидетельствуют, что очевидные алгоритмы не всегда наилучшие, а также потому, что могут служить основой разработки еще более эффективных и действительно практических алгоритмов для этого важного класса задач. 6.1. ОСНОВНЫЕ ПОНЯ1ИЯ В настоящем разделе приводятся основные алгебраические понятия, полезные прн изучении задач умножения матриц. Читатель, знакомый с кольцами и линейной алгеброй, может сразу перейти к равд. 6.2.
Гл. е. умножинии мАтРиц Определение. Кольцом называется алгебраическая структура (5, +,, О, 1), где 5 — множество элементов, а+ н ° — бинарные операции на нем. Для каждых а, Ь и с из 5 выполняются следующие соотношения: 1) (а+Ь)+с=а+(Ь+с) и (а Ь) с=а (Ь.с) (операции + и ° ассоциативны); 2) а+Ь=Ь+а (операция + коммутативна); 3) (а+Ь) с=а с+Ь сиа (Ь+с)=а Ь+а с(операция ° дистрибутивна относительно +); 4) а+0=0+а=а (О служит единичным элементом для +); 5) а 1 1 ° а а (1 служит единичным элементом для ); 6) для каждого а ~5 существует обратный элемент — а, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
