Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
SearchR(G, 0, 6) 0-1 searchR(G, 1, 6) 1-0 1-2 0-2
|
|
SearchR(G, 5, 6) 5-0
SearchR(G, 4, 6) 4-2
SearchR(G, 3, 6) 3-2 3-4 4-6 searchR(G, 6, 6)
РИСУНОК 17.17. ТРАССИРОВКА ПОИСКА ПРОСТОГО ПУТИ
Данная трассировка показывает, как работает рекурсивная функция из программы 17.16 на примере вызова searchR(G, 2, 6) с целью поиска простого пути из вершины 2 в вершину б на графе, который показан в верхней части рисунка. Для каждого исследуемого ребра в трассе отводится отдельная строка с отступом на один уровень для каждого рекурсивного вызова. Чтобы проверить ребро 2-0, мы осуществляем вызов searchR(G, 0, 6). Этот вызов заставляет нас проверить ребра 0-1, 0-2 и 0-5. Чтобы проверить ребро 0-1, мы делаем вызов searchR(G, 1, 6), который заставляет нас проверить ребра 1-0 и 1-2, которые не приводят к рекурсивным вызовам, поскольку вершины 0 и 2 уже помечены. В этом примере рассматриваемая функция обнаруживает путь 2-0-5-4-6.
Часть 5. Алгоритмы на графах
| ти один раз? Если этот путь приводит в ту же вершину, из которой он вышел, то эта задача известна как задача поиска гамильтонова цикла. Существует ли цикл, который проходит через каждую вершину в точности один раз? На первый взгляд, кажется, что эта задача решается просто: достаточно внести некоторые простые изменения в рекурсивную часть класса, осуществляющего поиск пути, который показан в программе 17.16. Однако, эта программа, по-видимому, не может быть пригодной для всех графов, поскольку время ее прогона в худшем случае находится в экспоненциальной зависимости от числа вершин в графе. Программа 17.17. Гамильтонов путь___________________________________________________ Данная рекурсивная функция отличается от используемой в программе 17.16 всего лишь в двух отношениях: во-первых, она принимает длину искомого пути в качестве третьего аргумента и возвращает значение, означающее успех, только в случае, если находит путь длины V; во-вторых, она переустанавливает значение маркера visited, прежде чем возвратит значение, означающее неуспех. Если мы заменим рекурсивную функцию, используемую программой 17.16, на приводимую ниже и добавим третий аргумент G, V()-1 в вызов функции searchR из функции search, то search будет выполнять поиск гамильтонова пути. Однако не рассчитывайте, что поиск будет выполнен до конца, если только он не проводится на графах совсем небольших размеров (см. рассуждения по тексту раздела). |
Мы проведем подробные исследования алгоритма поиска в глубину в его более общей формулировке в следующем разделе, там же мы рассмотрим несколько других алгоритмов связности. Например, несколько более общая версия программы 17.16 предлагает нам способ обхода всех ребер графа путем построения вектора, индексированного именами вершин, который позволяет клиенту проверить за постоянное время, существует ли путь, соединяющий какие-либо две вершины.
Свойство 17.2 дает существенно завышенную оценку фактического времени прогона программы 17.16, поскольку она может найти путь после исследования всего лишь нескольких ребер. В данный момент все, что нас интересует, это освоение метода, который гарантированно обеспечивает определение пути, соединяющего любые пары вершин любого графа за линейное время. В отличие от этого, другие задачи, которые на первый взгляд мало чем отличаются от рассматриваемой проблемы, намного труднее поддаются решению. Например, рассмотрим следующую задачу, в рамках которой мы осуществляем поиск пути, соединяющих пары вершин, но при этом добавляется условие, согласно которому эти пути проходят через все остальные вершины графа.
Гамильтонов путь. Пусть даны две вершины, существует ли простой путь, соединяющий эти вершины, который проходит через каждую вершину графа в точное-
РИСУНОК 17.18. ГАМИЛЬТОНОВ ПУТЬ
В графе, помещенном в верхней части рисунка, имеется гамильтонов путь 0-6-4-2-1-3-5-0, который заходит в каждую вершину в точности один раз и возвращается в ту вершину, в которой он начинался; в то же время, граф в нижней части рисунка такого пути не содержит.
Глава 17, Свойства и типы графов
bool searchR (int v, int w, int d) {
if (V == w) return (d == 0); visited [v] = true;
typename Graph:: adjIterator A(G, v); for (int t = A.beg();! A.end(); t = A.nxt()) if (! visited[t])
if (searchR(t, w, d-l)) return true; visited[v] = false; return false/ }
Свойство 17.3. Рекурсивный поиск гамильтонова цикла может потребовать экспоненциального времени.
Доказательство: Рассмотрим граф, у которого вершина V-1 изолирована, а ребра, связывающие остальные V — 1 вершин, образуют полный граф. Программа 17.17 никогда не найдет гамильтонова пути, в то же время, применив метод индукции, легко убедиться в том, что она исследует все (V— 1)! путей в полном графе, каждый из которых требует V— 1 рекурсивных вызовов. Следовательно, общее число рекурсивных вызовов равно V! или примерно (V/e)v, что больше, чем любая константа в V-той степени. ■
Полученные нами реализации - программа 17.16, осуществляющая поиск простых путей, и программа 17.17, выполняющая поиск гамильтоновых путей, - очень похожи друг на друга. Если таких путей не существует, выполнение обеих программ прекращается, когда всем элементам вектора visited установлено значение true. Почему времена прогона этих программ столь разительно отличаются друг от друга? Прогон программы 17.16 гарантированно выполняется за короткое время, поскольку она устанавливает, по меньшей мере, один элемент вектора visited в 1 всякий раз, когда вызывается функция searchR. С другой стороны, программа 17.17 может устанавливать элементы вектора visited снова в 0, так что мы не можем гарантировать, что ее выполнение завершится скоро.
Выполняя поиск простых путей с помощью программы 17.16, мы знаем, что если существует путь из v в w, мы найдем его, выбирая одно из ребер v-t, исходящее из v; то же можно сказать и о гамильтоновых путях. Но на этом сходство заканчивается. Если мы не можем найти простой путь из t в w, то приходим к выводу, что простого пути из v в w, проходящего через t, не существует; однако такая ситуация в процессе поиска гамильтонова пути не возникает. Может случиться так, что в графе нет гамильтонова пути в вершину w, который начинается с ребра v-t, но есть путь, который начинается с v-x-t и проходит через вершину х. Мы должны выполнять рекур-
РИСУНОК 17.19. ТРАССИРОВКА ПОИСКА ГАМИЛЬТОНОВА ПУТИ
Эта трассировка показывает ребра, проверенные программой 17.17 для того, чтобы убедиться, что граф, приведенный в верхней части рисунка, не имеет гамильтонова цикла. Для краткости ребра, входящие в помеченные вершины, опущены.
Часть 5. Алгоритмы на графах
|
| сивные вызовы из t, соответствующие каждому пути, который ведет в нее из вершины v. Короче говоря, нам, возможно, придется проверить каждый путь в графе. Полезно задуматься над тем, насколько медленно действующим является алгоритм, время выполнения которого пропорционально факториалу количества вершин. Допустим, что мы можем обработать граф с 15 вершинами за 1 секунду, тогда обработка графа с 19 вершинами будет длиться целые сутки, более года, если граф содержит 21 вершину, и 6 столетий, если граф содержит 23 вершины. Увеличение быстродействия компьютера мало чем может помочь. Если повысить быстродействие компьютера в 200000 раз, то для решения рассматриваемой задачи с 23 вершинами ему потребуется больше суток. Стоимость обработки графа с 100 или 1000 вершинами такова, что страшно подумать, не говоря уже о графах, с которыми нам приходится сталкиваться на практике. Потребуются многие миллионы страниц этой книги, чтобы только записать число веков, в течение которых будет длиться обработка графа, содержащего миллионы вершин. В главе 5 мы провели исследование некоторого числа простых рекурсивных программ, которые по характеру подобны программе 17.17, однако качество этих исследований можно было существенно повысить за счет применения нисходящего динамического программирования. Данная рекурсивная программа по своему характеру полностью от них отличается: количество промежуточных результатов, которые требуется сохранять в памяти, возрастает по экспоненте. Несмотря на то что многие исследователи затрачивают громадные усилия на решение этой задачи, ни одному из них |
еще не удалось найти алгоритм, который обеспечивал приемлемую производительность при обработке графов больших (и даже средних) размеров.
Теперь предположим, что мы изменили начальные условия, и требование обязательного обхода всех вершин заменяется требованием обхода всех ребер. Является ли эта задача такой же легкой, как и нахождение простых путей, или безнадежно трудной проблемой, подобной поиску гамильтоновых путей?
Эйлеров путь. Существует ли путь, соединяющий две заданных вершины, который проходит через каждое ребро графа в точности один раз? Путь не обязательно должен быть простым — вершины можно посещать многократно. Если путь начинается из некоторой вершины и возвращается в ту же вершину, мы имеем задачу поиска эйлерова цикла (Euler tour). Существует ли циклический путь, который проходит через каждое ребро графа в точности один раз? В следствии к свойству 17.4 мы докажем, что задача поиска такого пути эквивалентна задаче поиска цикла в графе, построенного путем добавления в граф ребра, соединяющего две соответствующие вершины. На рис. 17.20 приводятся два небольших примера.
Первым эту классическую задачу исследовал Л.Эйлер (L.Euler) в 1736 г. Некоторые математики склонны считать, что начало исследованию графов и теории графов
РИСУНОК 17.20. ПРИМЕРЫ ЭЙЛЕРОВЫХ ЦИКЛОВ И ЦЕПЕЙ
Граф, показанный в верхней части рисунка, содержит эйлеров цикл 0-1-2-0-6-4-3-2-5-0, который использует все ребра в точности один раз. Граф, изображенный в нижней части рисунка, не содержит таких циклов, однако содержит эйлеров путь 0-2-0-1-3-4-2-3-5-4-6-0-5.