![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. являются шаблонами многочисленных алгоритмов, обладающих этим свойством
Кратчайший путь. Найти кратчайший путь на графе, ведущий из v в w. Мы можем решить эту задачу, инициируя процесс поиска в ширину, который поддерживает в вершине v представление st дерева поиска в виде родительских связей, прекращая этот процесс по достижении вершины w. Путь из w в v вверх по дереву и является самым коротким. Например, после построения объекта bfs класса BFS< Graph> может использовать следующий программный код для распечатки пути, ведущего из w в v: for (t = w; t! =w; t = bfs.ST(t)) cout «t «" -"; cout «v «endl; Чтобы получить путь v в w, замените в этом узле операцию cout на операцию заталкивания индексов в стек, затем войдите в цикл, который распечатывает индексы этих вершин после выталкивания их из стека. Либо начните поиск в w и остановите его тогда, когда v окажется на первом месте. Кратчайший путь из единственного источника. Найти кратчайшие пути, соединяющие заданную вершину v со всеми другими вершинами графа. Полное дерево с корнем в вершине v позволяет решить эту задачу: путь из каждой вершины, ведущий в корень есть кратчайший путь в корень. Поэтому, чтобы решить эту задачу, мы выполняем поиск в ширину до завершения, начиная с v. Вектор st, который появляется в результате таких вычислений, есть представление дерева BFS в виде совокупности родительских связей, а программный код, показанный чуть выше, позволяет получить кратчайшие пути для любой другой вершины w. Кратчайшие пути для всех пар вершин. Найти кратчайший путь, соединяющий каждую пару вершин графа. Способ решения этой задачи предусматривает использование класса BFS, который решает задачу единственного источника для каждой вершины фа-фа и поддерживает функции-элементы, которые способны эффективно выполнить обработку громадного числа запросов на вычисление кратчайших путей за счет сохранения представлений длин путей и дерева родительских связей для каждой вершины (см. рис. 18.23). Такая предварительная обработка требует времени, пропорционального VE, и пространства памяти, пропорционального V2, что делает невозможной обработку крупных разреженных графов. Тем не менее, она позволяет строить АТД с оптимальными рабочими характеристиками: после определенных затрат ресурсов на предварительную обработку (и пространства памяти для сохранения результатов такой обработки), можно вычислить длины кратчайших путей за постоянное время, а сами пути - за время, пропорциональное их длине (см. упражнение 18.55). Такие решения, полученные благодаря применению поиска в ширину, достаточно эффективны, однако здесь мы не будем рассматривать дополнительные подробности, поскольку они представляют собой специальные случаи алгоритмов, которые будут исследоваться в главе 21. Понятие кратчайшего пути (shortest path) в графе в общем случае используется для описания соответствующих задач в орграфах и сетях. Часть 5. Алгоритмы на графах
РИСУНОК 18.23. ПРИМЕР ПОИСКА КРАТЧАЙШИХ ПУТЕЙ ДЛЯ ВСЕХ ПАР ВЕРШИН Изображенные на данном рисунке диаграммы описывают результат выполнения поиска в ширину из каждой вершины, благодаря чему производится вычисление кратчайших путей, соединяющих все пары вершин. Каждый поиск приводит к построению дерева BFS, которое определяет кратчайшие пути, соединяющие все вершины графа с вершиной в корне дерева. Результаты всех выполненных поисков сводятся в две матрицы, показанные в нижней части рисунка. В левой матрице элемент на пересечении строки v и столбца v представляет длину кратчайшего пути из v в w (глубина v в дереве w). Каждая строка правой матрицы содержит массив st для соответствующего поиска. В условиях рассматриваемого примера кратчайший путь из 3 в 2 состоит из трех ребер, как показывает элемент левой матрицы, расположенный на пересечении строки 3 и столбца 2. Третье сверху слева дерево BFS говорит нам, что таким путем является 3-4-6-2, и эта информация закодирована в строке 2 матрицы справа. Матрица не обязательно должна быть симметричной, когда существуют несколько кратчайших путей, поскольку обнаруженные пути зависят от порядка выполнения поиска в ширину. Например, дерево BFS, показанное внизу слева, и строка 3 правой матрицы говорят нам, что кратчайшим путем из 2 в 3 является 2-0-5-3. Глава 18. Поиск на графе
Базовые характеристики динамики поиска резко контрастируют с аналогичными характеристиками поиска в глубину, что и демонстрирует большой граф, изображенный на рис. 18.24, если его сравнить с рис. 18.13. Дерево имеет небольшую глубину, зато обладает протяженной шириной. Оно может служить иллюстрацией множества особенностей, которыми поиск в ширину на графе отличается от поиска в глубину. Например: ■ Существует относительно короткий путь, соединяющий каждую пару вершин ■ Во время поиска большая часть вершин будет смежными со множеством непосе Опять-таки, этот пример типичен для поведения, которое мы ожидаем от поиска в ширину, однако проверка факта, что такими особенностями обладают модели графов, представляющие для нас интерес, и графы, с которыми приходится сталкиваться на практике, требует подробного анализа. Поиск в глубину прокладывает свой путь в графе, запоминая в стеке точки, в которых произрастают другие пути; поиск в ширину проходит по графу, используя очередь для запоминания границ, которых он достиг. Поиск в глубину исследует граф, осуществляя поиск вершин, расположенных на значительном удалении от исходной точки, принимая к рассмотрению более близкие вершины только в случаях выхода на безусловные тупики. РИСУНОК 18.24. ПОИСК В ШИРИНУ Данный рисунок служит иллюстрацией того, что поиск в ширину протекает в случайном эвклидовом графе с близкими связями (слева) в том же стиле, что и показанный на рис. 18.13. Как легко видеть из этого примера, дереву BFS свойственна малая глубина и большая ширина на рассматриваемом типе графа (а также для многих других типов графов, которые часто встречаются на практике). Иначе говоря, в рассматриваемом случае вершины соединены между собой, в основном, короткими путями. Различие между формами деревьев DFS и BFS свидетельствуют о существенном различии динамических характеристик этих алгоритмов.
|