Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19, Орграфы и ориентированные ациклические графы. В алгоритмах поиска на графах общего вида применительно к неориентированным графам мы используем тот же интерфейс
|
|
В алгоритмах поиска на графах общего вида применительно к неориентированным графам мы используем тот же интерфейс, что и для случая связности (см. программу 18.4). Назначение наших алгоритмов состоит в том, чтобы присвоить номер компоненты каждой вершине вектора, индексированного по именам вершин, используя с этой целью метки О, 1,... для обозначения сильных компонент. Наибольший из присваиваемых номеров есть номер, который на единицу меньше количества сильных компонент, а мы можем использовать номер компоненты для проведения проверки, входят ли две заданные вершины в одну и ту же сильную компоненту, за постоянное время.
Алгоритм решения этой задачи " в лоб" построить нетрудно. Используя АТД абстрактного транзитивного замыкания, проанализируйте каждую пару вершин s и t с тем, чтобы проверить, достижима ли вершина t из s и достижима ли s из t Определите неориентированный граф, в котором содержатся ребра для каждой такой пары: связные компоненты этого графа суть сильные компоненты орграфа. Этот алгоритм нетрудно описать и реализовать, а время его выполнения в основном затрачивается на реализацию абстрактно-транзитивного замыкания таким, каким оно описано, скажем, свойством 19.10.
Алгоритмы, которые мы рассмотрим в данном разделе, являются воплощением последних достижений в области построения алгоритмов, они способны обнаружить сильные компоненты любого графа за линейное время, т.е. в V раз быстрее, чем алгоритм решения " в лоб". Для графов, содержащих 100 вершин быстродействие этих алгоритмов в 100 раз быстрее, чем алгоритм решения этой задачи " в лоб"; для графа с 1000 вершин они работают в 1000 раз быстрее; и у нас появляется возможность решать задачи такого рода для графов с миллионами вершин. Эта задача является красноречивым примером возможностей хорошего алгоритма, она стала мощным побудительным мотивом на проведение исследований в области алгоритмов на графах. В каких других областях мы можем рассчитывать на сокращение используемых ресурсов в миллион и более раз за счет выбора элегантного алгоритма решения практически важной задачи?
История этой задачи сама по себе достаточно поучительна (см. раздел ссылок). В пятидесятые и шестидесятые годы математики и специалисты по вычислительной технике приступили к серьезному изучению алгоритмов на графах в контексте, в котором анализ алгоритмов сам развивался как отдельная область исследований. В условиях широкого разнообразия алгоритмов на графах, требовавшего исследований на фоне непрерывного и стремительного развития компьютерных систем, языков программирования и нашего понимания того, что означает выполнить эффективные вычисления, многие задачи оставались нерешенными. По мере того, как теоретики вычислительных систем стали постигать многие из базовых принципов анализа алгоритмов, они стали понимать, какие задачи на графах могут быть решены эффективно и для каких задач это невозможно, и приступили к разработке алгоритмов решения прежнего набора задач и к повышению их эффективности. И действительно, Р. Тарьян (R. Tarjan) предложил линейные по времени выполнения алгоритмы решения задачи сильной связности и других задач на графах в 1972 году, в том самом, когда Р. Карп (R. Karp) доказал невозможность эффективного решения задачи коммивояжера и многих других задач на графах. Алгоритм Тарьяна оставался главным направлением анализа алгоритмов в течение многих лет, поскольку он решает важную практическую задачу, используя для этой цели простые структуры данных. В восьмидесятых годах Р. Косарайю (R. Kosaraju) предложил оригинальный подход к ре-
Часть 5. Алгоритмы на графах
шению этой задачи и разработал ее новое решение; несколько позднее было установлено, что статья, в которой был описан этот же метод, была опубликована в научной печати в России намного раньше, а именно, в 1972 г. Позже, в 1999 г., Г. Габову (Н. Gabov) удалось получить простую реализацию одного из первых подходов, предложенных в шестидесятых года, что дает третье линейное по времени решение этой задачи.
Суть сказанного выше состоит не только в том, что трудные задачи обработки графов могут иметь простые решения, но и в том, что абстракции, которыми мы пользуемся (поиск в глубину и списки смежных вершин) таят в себе гораздо большие возможности, чем мы можем предполагать. По мере того как мы освоим эти и подобные им инструментальные средства, нас не должны также удивлять случаи обнаружения простых решений других важных задач на графах. Исследователи продолжают поиски компактных реализаций, подобных рассматриваемым выше, других многочисленных важных алгоритмов на графах; многие из таких алгоритмов еще предстоит открыть.
Метод Косарайю прост для понимания и реализации. Чтобы найти сильные компоненты заданного графа, сначала выполняется поиск в глубину в обратном порядке, что означает вычисление различных перестановок вершин, определенных посредством нумерации при обходе в обратном порядке. (Такой процесс представляет собой топологическую сортировку, если орграф есть DAG.) Затем производится прогон DFS на этом графе, но на этот раз с целью обнаружить следующую вершину для поиска (при вызове рекурсивной функции поиска в начале прогона и каждый раз, когда рекурсивная функция поиска возвращает результат в функцию поиска более высокого уровня) используется непосещенная вершина с максимальным номером в обратном порядке.
Привлекательность такого алгоритма заключается в том, что когда проверка непосещенных вершин производится в соответствии с топологической сортировкой таким образом, деревья в лесе DFS определяют сильные компоненты так же, как деревья в лесе DFS определяют связные компоненты в неориентированных графах — две вершины содержатся в одной и той же сильной компоненте тогда и только тогда, когда они принадлежат одному и тому же дереву в этом лесе. Рисунок 19.28 служит иллюстрацией этого факта в условиях рассматриваемого примера, что мы и докажем немного позже. В силу этого обстоятельства мы можем обозначать компоненты номерами, как это делалось в случае неориентированных графов, увеличивая номер компоненты на единицу всякий раз, когда рекурсивная функция возвращает результат в функцию поиска более высокого уровня. Программа 19.10 предлагает полную реализацию этого метода.
Программа 19.10. Сильные компоненты (алгоритм Косарайю)________________________
Клиенты могут использовать объекты этого класса для определения числа сильных компонент орграфа (count) и выполнять проверку на принадлежность сильной компоненте (strongly connected). Конструктор SC сначала строит обратный орграф и выполняет поиск в глубину с целью вычисления нумерации при обходе в обратном порядке. Далее он выполняет поиск в глубину на исходном орграфе, используя для этой цели обращение обратного порядка, полученного в результате выполнения первого поиска в глубину в цикле поиска, в котором производятся вызовы этой рекурсивной функции. Каждый рекурсивный вызов в рамках второго поиска в глубину посещает все вершины сильной компоненты.
|
|