Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19, Орграфы и ориентированные ациклические графы
|
|
19.10. Перспективы
В настоящей главе мы рассматривали алгоритмы решения задач топологической сортировки, транзитивного замыкания и нахождения кратчайшего пути для орграфов и для графов DAG, в том числе и фундаментальные алгоритмы выявления циклов и сильных компонент в орграфах. Эти алгоритмы находят многочисленные важные приложения сами по себе, а также служат основой решения более сложных задач, включая взвешенные графы, которые мы будем рассматривать в двух следующих главах. Значения времени прогона этих алгоритмов в худших случаях суммируются в таблице 19.3.
Таблица 19.3. Затраты на выполнение операций обработки орграфов в худшем случае
В эту таблицу сведены итоговые данные затратах (время выполнения в худшем случае) на выполнение алгоритмов решения различных задач обработки орграфов, рассмотренных в этой главе, для случайных графов и графов, в которых ребра случайным образом соединяет каждую вершину с одной из 10 заданных соседних вершин. Все затраты определялись на представлении графов в виде списков смежных вершин; в случае представления графа в виде матрицы смежности Е элементов становятся V2 элементами, поэтому, например, затраты на вычисление всех кратчайших путей составляют V3. Линейные по времени алгоритмы суть оптимальные алгоритмы, так что затраты позволяют с достаточной уверенностью предсказывать время выполнения при любом вводе; другие алгоритмы дают оценку с чрезмерным запасом затрат, таким образом, время выполнения для некоторых типов графов может оказаться ниже. Рабочие характеристики алгоритма вычисления транзитивного замыкания орграфа, обладающего наибольшим быстродействием, зависит от структуры орграфа, в частности, от размеров его базового DAG.
Часть 5. Алгоритмы на графах
В частности, общей темой на протяжении данной главы является решение задачи абстрактно-транзитивного замыкания, при этом мы хотели обеспечить поддержку АТД, который, после предварительной обработки, может определить, существует ли ориентированный путь из одной заданной вершины в другую. Несмотря на то что нижняя граница определяет, что затраты на предварительную обработку в худшем случае существенно превосходят V2, метод, обсуждавшийся в разделе 19.7, показывает, что базовые методы, исследуемые в этой главе, сводятся к простому решению, которое обеспечивает оптимальную производительность на многих типах орграфах; более-менее заметное исключение составляют лишь насыщенные графы DAG. Нижняя граница предполагает, что более высокая гарантированная производительность едва ли может быть достигнута на всех графах, в то же время мы можем пользоваться этими методами, чтобы получить приемлемую производительность на графах, встречающихся на практике.
Цель разработки алгоритмов с рабочими характеристиками, аналогичными характеристиками алгоритма объединения-поиска, который изучался в главе 1, для насыщенных орграфов остаются призрачными. В идеальном случае мы могли бы определять АТД, посредством которого мы могли бы добавлять ориентированные ребра или проверять, достижима ли одна вершина из другой, и разработать реализацию, в которой мы могли бы поддерживать выполнение всех операций за постоянное время (см. упражнения 19.153~19.155). Как отмечалось в главе 1, мы можем достаточно близко подойти к этой цели в случае неориентированных графов, но сравнимые с этим решения для орграфов или графов DAG до сих пор не известны. (Обратите внимание на тот факт, что удаление ребер представляет собой сложную проблему даже для неориентированных графов.) Эта задача динамической достижимости (dynamic reachability) не только вызывает интерес у математиков и имеет широкое практическое применение, но и играет исключительно важную роль в разработке алгоритмов на более высоком уровне абстракции. Например, достижимость лежит в основе задачи реализации сетевого симплексного алгоритма для определения потоков с минимальной стоимостью, представляющей собой модель решения задач, которая получила широкое применение и которую мы будем рассматривать в главе 22.
Множество других алгоритмов обработки орграфов и графов DAG находят важное практическое применение и подвергаются подробным исследованиям, в то же время многие задачи обработки орграфов ждут своих исследователей, способных разработать эффективные алгоритмы их решения. Список таких задач достигает внушительных размеров.
Доминаторы. Пусть задан DAG все, вершины которого достижимы из одного истока r, вершина v доминирует (dominates) над вершиной t, если каждый путь из rв t содержит s. (В частности, каждая вершина доминирует сама над собой.) Каждая вершина v, отличная от источника, имеет непосредственного доминатора, который доминирует над вершиной v, но в то же время не доминирует над другим доминатором v и над самим собой. Множество непосредственных доминаторов представляет собой дерево, которое охватывает все вершины, достижимые из источника. Эта структура имеет важное значение для построения компиляторов. Доминаторное дерево может быть вычислено за линейное время путем применения подхода, основанного на поиске в глубину, который использует несколько вспомогательных структур данных, хотя обычно на практике применяется несколько более медленная его версия.