Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 136
Текст из файла (страница 136)
(Указание: можно воспользоваться подпрограммой сжатия множеств ребер, как в процедуре МБТ йюпсн, описанной в задаче 23-2.) 23-4. Альтернативные алгоритмы поиска минимальных остовиых деревьев В этой задаче мы приведем псевдокоды трех различных алгоритмов. Каждый из них принимает в качестве входных данных граф и возвращает Глава 23. Минимальные остовные деревья 661 множество ребер Т.
Для каждого из алгоритмов требуется доказать, что Т является минимальным остовным деревом графа, или доказать, что это не так. Кроме того, опишите эффективную реализацию каждого из алгоритмов, независимо от того, вычисляет он минимальное остовное дерево или нет. а) Мм'вн МБТ А(с.,ю) 1 Сортируем ребра в невозрастающем порядке весов 2 Т+ — Е 3 1ог (Для) каждого ребра е в отсортированном порядке 4 йо!Г Т вЂ” (е) — связный граф 5 гйеп Т Т вЂ” (е) 6 гегнгп Т б) МАтвн МБТ В(С,ю) 1 Т+ — 11 2 1ог (Для) каждого ребра е в произвольном порядке 3 бо 1Г Т 0 (е) не имеет циклов 4 Феп Т вЂ” Т 0 (е) 5 геГпгп Т в) МАУВЕ МБТ С(а,ю) 1 Т+-6 2 Гог (Для) каждого ребра е в произвольном порядке 3 йоТ вЂ” Т0(е) 4 1Г Т имеет цикл с 5 гЬеп Пусть е' — ребро максимального веса в с 6 Т Т вЂ” (е') 7 гегпгп Т Заключительные замечания Книга Таржана (Тат)ап) [292] содержит превосходный обзор задач, связанных с поиском минимальных остовных деревьев, и дополнительную информацию о них.
История данной задачи изложена Грехемом (ОгаЬагп) и Хеллом (Не!1) [131]. Таржан указывает, что впервые алгоритм для поиска минимальных остовных деревьев был описан в 1926 году в статье Борувки (О. Вогйчка). Его алгоритм состоит в выполнении 0(1яЪ') итераций процедуры МБТ Кнгнэсе, описанной в задаче 23-2. Алгоритм Крускала описан в [195] в 1956 году, а алгоритм, известный как алгоритм Прима, — в работе Прима (Рпгп) [250], хотя до этого он был открыт Ярником (1агпрк) в 1930 году. Часть Ч1. Алгоритмы для работы с графами Причина, по которой жадные алгоритмы эффективно решают задачу поиска минимальных остовных деревьев, заключается в том„что множество лесов графа образует матроид (см.
раздел 16.4). Когда ~Е~ = П(Ъ'18У), алгоритм Прима, реализованный с использованием фибоначчиевых пирамил, имеет время работы О (Е). Для более разреженных графов использование комбинации идей из алгоритма Прима, алгоритмов Крускала и Борувки, вместе с применением сложных структур данных дало возможность Фредману (Ргедшап) и Таржану [98) разработать алгоритм, время работы которого равно О (Е 18' У). Габов (баЬотч), Галил (Пай)„Спенсер (Брепсег) и Таржан [102) усовершенствовали этот алгоритм, доведя время его работы до О (Е 18 18' 1'). Чазел (СЬахе1!е) [53) разработал алгоритм, время работы которого — О (Еа (Е, 1~)), где а(Е, 1') — функция, обратная функции Аккермана (см. главу 21). В отличие от перечисленных ранее, алгоритм Чазела не является жадным. С задачей поиска минимального остовного дерева связана задача проверки осюноелого дерека (зраппшй 1гее чег[бсайоп), в юторой для данного графа О = = (ч'", Е) и дерева Т С Е требуется определить, является ли Т минимальным остовным деревом С.
Кинг (Кшй) [177) разработал алгоритм решения данной задачи за линейное время, основанный на работах Комлеса (Кош1оз) [188) и Диксона (131хоп), Рауха (КаисЬ) и Таржана [77). Все описанные выше алгоритмы детерминированные и относятся к модели на основе сравнений, описанной в главе 8. Каргер (Кагйег), Клейн (К1еш) и Таржан [169) разработали ранломизированный алгоритм поиска минимальных остовных деревьев, математическое ожидание времени работы которого — О (Ъ'+ Е). Этот алгоритм использует рекурсию наподобие алгоритма с линейным временем работы из раздела 9.3: рекурсивный вызов для вспомогательной задачи определяет подмножество ребер Е', которое не может находиться ни в одном минимальном остовном дереве.
Другой рекурсивный вызов, работаюший с подмножеством Š— Е', строит минимальное остовное дерево. Алгоритм также использует идеи из алгоритмов Борувки и Кинга. Фредман н Виллард (тч1!!агд) [100) показали, как найти минимальное остовное дерево за время О (У+ Е) с использованием детерминированного алгоритма, не основанного на сравнениях. Их алгоритм предполагает, что данные представляют собой Ь-битовые целые числа и что память юмпьютера состоит из адресуемых Ь- битовых слов. ГЛАВА 24 Кратчайшие пути из одной вершины Водителю автомобиля нужно найти как можно более короткий путь из Киева в Запорожье.
Допустим, у него есть карта Украины, на которой указаны расстояния между каждой парой пересечений дорог. Как найти кратчайший маршрут? Один из возможных способов — пронумеровать все маршруты из Киева в Запорожье, просуммировать длины участков на каждом маршруте и выбрать кратчайший из них. Однако легко понять, что даже если исключить маршруты, содержащие циклы, получится очень много вариантов, большинство которых просто не имеет смысла рассматривать.
Например, очевидно, что маршрут из Киева в Запорожье через Львов — далеко не лучший выбор. Точнее говоря, такой маршрут никуда не годится, потому что Львов находится относительно Киева совсем в другой стороне. В этой главе и в главе 25 будет показано, как эффективно решаются такие задачи. В задаче о кратчайшем луши (злоггем-рагпз ргоЫеш) задается взвешенный ориентированный граф С = (У, Е) с весовой функцией ш: Е -> К, отображающей ребра на их веса, значения которых выражаются действительными числами.
Вес (~че1йлг) пути р = (се, иы..., сь) равен суммарному весу входящих в него ребер: Часть Ч!. Алгоритмы для работы с графами Вес кратчайшего пути (з)зопез!-раба ~че(к(п) из вершины и в вершину п опреде- ляется соотношением п пп ~ю (р): и -+ о~ если имеется путь от и к и, р д(и,с) = 00 в противном случае. Тогда по определению крат чайигий путь (з!юпез! ра!)з) из вершины и в вершину о — это любой путь, вес которого удовлетворяет соотношению ю (р) = б (и, о). В примере, в котором рассматривается маршрут из Киева в Запорожье, карту дорог можно смоделировать в виде графа, вершины которого представляют перекрестки дорог„а ребра — отрезки дорог между перекрестками, причем вес каждого ребра равен расстоянию между соответствующими перекрестками.
Цель — найти кратчайший путь от заданного перекрестка в Киеве (например, между улицамн Клавдиевской и Корсуньской) к заданному перекрестку в Запорожье (скажем, между улицами Панфиловцев и Патриотической). Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму. Алгоритм поиска в ширину, описанный в разделе 22.2, представляет собой алгоритм поиска кратчайшего пути по невзвешенному графу, т.е. по графу, каждому ребру которого приписывается единичный вес. Поскольку многие концепции, применяющиеся в алгоритме поиска в ширину, возникают при исследовании задачи о кратчайшем пути по взвешенным графам, рекомендуется освежить в памяти материал раздела 22.2.
Варианты Настоящая глава посвящена задаче о кратчайшем пути из одной вершины (з(пд!е-зопгсе йопез!-рагпз ргоЫеш), в которой для заданного графа С = ()г, Е) требуется найти кратчайший путь, который начинается в определенной исходной вершине (зопгсе чег!ех) в Е Ъ' (для краткости будем именовать ее истоком) и заканчивается в каждой из вершин о е Ъ'. Предназначенный для решения этой задачи алгоритм позволяет решить многие другие задачи, в том числе те, что перечислены ниже.
° Задача о кратчайшем пути в заданный пункт назначения (з1пя1е4езбпабоп з)зопез!-рабзз ргоЫегп). Требуется найти кратчайший пугь в заданную вершину назначения (безппа!юп чепех) 1, который начинается в каждой нз вершин о. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине. Глава 24. Кратчайшие пути из одной вершины 665 ° Задача о кратчайшем пути между заданной парой вершин (з1пя!е-ра1г зЬопезыраг1зз ргоЫеш). Требуется найти кратчайший путь из заданной вершины и в заданную вершину и. Если решена задача о заданной исходной вершине и, то эта задача тоже решается.
Более того, для этой задачи не найдено нн одного алгоритма, который бы в асимптотическом пределе был производительнее, чем лучшие из известных алгоритмов решения задачи об одной исходной вершине в наихудшем случае. ° Задача о кратчайшем пути между всеми парами вершин (а11-рава йопезь ра11зз ргоЫет). Требуется найти кратчайший путь из каждой вершины и в каждую вершину ш Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
