Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. лах от 0 до V— 1. Результатом, скорее всего, будет произвольный мультиграф с петлями
лах от 0 до V— 1. Результатом, скорее всего, будет произвольный мультиграф с петлями. Заданной парой может оказаться два идентичных числа (отсюда получаются петли); при этом одна и та же пара может повторяться многократно (отсюда получаются параллельные ребра). Программа 17.12 генерирует ребра до тех пор, пока не станет известно, что число ребер в графе достигло значения Е, при этом решение об удалении параллельных ребер остается за реализацией. Если параллельные ребра удалены, то число полученных при генерации ребер должно быть значительно больше, чем число ребер (Е), использованных в насыщенных графах (см. упражнение 17.62); в силу отмеченных особенностей этот метод обычно используется для разреженных графов. Программа 17.13. Генератор случайных графов (случайный граф)_____________________ Как и в программе 17.13, рассматриваемая функция генерирует пары случайных целых чисел в диапазоне от 0 до V-1 с тем, чтобы добавлять в граф произвольные ребра, однако она использует другую вероятностную модель, по условиям которой каждое возможное ребро появляется независимо от других с вероятностью р. Значение р вычисляется таким образом, чтобы ожидаемое число ребер (рV(V-1)/2) было равно Е. Число ребер в каждом конкретном графе, генерируемых этой программой, близко к Е, однако маловероятно, что оно будет в точности равно Е. Этот метод пригоден в основном применительно к насыщенным графам, поскольку время его выполнения пропорционально V2. static void randG (Graph & G, int E) { double p = 2.0*E/G.V()/(G.V()-l); for (int i = 0; i < G.V(); i++) for (int j = 0; j < i; j++) if (rand() < p*RAND_MAX) G. insert(Edge(i, j)); } Случайный граф. Классическая математическая модель случайных графов должна рассмотреть все возможные ребра и включить в граф каждое ребро с фиксированной вероятностью р. Если мы хотим, чтобы ожидаемое число ребер графа было равно E мы должны выбрать p = 2E/V(V— 1). Программа 17.13 реализует функцию, которая использует эту модель для генерации случайных графов. Эта модель не допускает дубликаты ребер, однако число ребер в графе равно Е только в среднем. Эта реализация хорошо подходит для насыщенных графов, но отнюдь не для разреженных графов, поскольку за время, пропорциональное V(V- l)/2, она генерирует Е = pV(V- l)/2 ребер. То есть, для разреженных графов время прогона программы 17.13 находится в квадратичной зависимости от размеров графа (см. упражнение 17.68). Эти модели хорошо изучены, а их реализация не представляет трудностей, однако они не обязательно генерируют графы со свойствами, подобные свойствам графов, наблюдаемым на практике. В частности, графы, которые моделируют карты, электронные схемы, расписания, транзакции, сети и другие реальные ситуации, обычно не только относятся к числу разреженных, но и проявляют свойство локальности — вероятность того, что заданная вершина соединена с одной из вершин конкретного множества вершин, выше, чем вероятность соединения с вершиной, не входящей в это множество. Мы можем обсуждать многие различные способы моделирования свойства локальности, как показывают следующие примеры. Глава 17. Свойства и типы графов
k-соседний граф. Граф, изображенный в верхней части рис. 17.13, вычерчен по результатам простых изменений, внесенных в генератор графов со случайными ребрами, в процессе которых мы случайным образом выбирали первую вершину v, затем также случайным образом выбирали следующую вершину из числа тех вершин, индексы которых попадали в диапазон, образованный некоторой постоянной к, с центром в v (циклический возврат от V— 1 до 0, когда вершины упорядочены в виде окружности, как показано на рис. 17.13). Генерация таких графов не представляет собой трудностей, они, безусловно, обладают свойством локальности, которое не характерно для случайных графов. Эвклидов граф с близкими связями. Граф, показанный в нижней части рис. 17.13, вычерчен генератором, который выбирает на плоскости V точек со случайными координатами в диапазоне от 0 до 1, а затем генерирует ребра, соединяющие две точки, удаленные друг от друга на расстояние, не превышающее d. Если d невелико, то граф получается разреженным, если d большое, то граф насыщенный (см. упражнение 17.74). Такой граф моделирует типы графов, с которыми мы обычно сталкиваемся при работе с картами, электронными схемами или другими приложениями, в условиях которых вершины привязаны к определенным геометрическим точкам. Их нетрудно представить наглядно, они позволяют подробно отобразить свойства алгоритмов и структурные свойства, которые обнаруживаются в приложениях подобного рода. Один из возможных недостатков этой модели состоит в том, что разреженные графы с большой долей вероятности могут не быть связными; другая связанная с ними трудность заключается в том, что маловероятно, чтобы они содержали вершины высокой степени, а также в том, что в них нет длинных ребер. При желании мы можем внести в эти модели соответствующие изменения, которые позволят нам найти выход из таких ситуаций, либо мы можем провести исследования многочисленных примеров подобного рода, чтобы попытаться смоделировать другие ситуации (см., например, упражнения 17.72 и 17.73). Опять-таки, мы можем протестировать наши алгоритмы на реальных графах. В условиях многих приложений РИСУНОК 17.13. СЛУЧАЙНЫЕ ГРАФЫ С БЛИЗКИМИ СВЯЗЯМИ Примеры, приводимые на этом рисунке, служат иллюстрацией двух моделей разреженных графов. Граф с близкими связями, изображенный в верхней части рисунка, содержит 33 вершины и 99 узлов, при этом каждое ребро может соединять заданную вершину с другой вершиной, индекс которой отличается от индекса заданной вершины не больше, чем на 10 (по модулю V). Эвклидов граф с близкими связями, показанный в нижней части рисунка, моделирует типы графов, которые мы можем найти в приложениях, в которых вершины привязаны к конкретным геометрическим точкам. Вершины изображены как случайные точки на плоскости; ребра соединяют любую пару вершин, расстояние между которыми не превышает d. Этот граф относится к категории разреженных (177 вершин и 1001 ребер); варьируя значения d, мы можем построить граф любой степени насыщенности. Часть 5. Алгоритмы на графах
фактические данные порождают массу примеров задач, которые мы с успехом можем использовать для тестирования наших алгоритмов. Например, крупные графы, полученные на базе реальных географических данных, встречаются довольно часто, еще два таких примера приводятся в последующих параграфах. Преимущество работы с фактическими данными, а не с моделями случайных графов, заключается в том, что мы можем находить решения реальных задач в процессе совершенствования алгоритмов. Недостаток определяется тем, что мы можем потерять привилегию оценивать производительность разрабатываемых нами алгоритмов, используя для этой цели методы математического анализа. Мы вернемся к этой теме в конце главы 18, когда будем готовы провести сравнение применения нескольких различных алгоритмов к решению одной и той же задачи. Граф транзакций. На рис. 17.14 показан всего лишь небольшой фрагмент графа, который мы можем обнаружить в компьютерах телефонной компании. В этом графе каждому телефонному номеру определяется собственная вершина, а каждое ребро, соединяющее пару i и j, наделено свойством, согласно которому i производит телефонный звонок j в течение некоторого фиксированного промежутка времени. Это множество ребер представляет собой мультиграф огромных размеров. Он, естественно, разрежен, поскольку каждый абонент охватывает своими звонками всего лишь мизерную часть установленных телефонов. Этот граф является представительным для многих приложений. Например, кредитная карточка финансового учреждения и запись в счете торгового агента могут содержать информацию аналогичного характера. Программа 17.14. Построение графа из пар символов Данная реализация функции scan из программы 17.4 использует таблицу символов для построения графа путем считывания пар символов из стандартного ввода. Функция index АТД таблицы символов ставит некоторое целое число в соответствие каждому символу: если поиск в таблице размера N закончится неудачно, она добавляет в таблицу символ с привязанным к нему целым числом N+1; если поиск завершится успешно, она просто возвращает целое число, которое ранее было ассоциировано с заданным символом. Любой из методов построения таблиц символов, рассмотренных в РИСУНОК 17.14. ГРАФ ТРАНЗАКЦИИ Последовательности пар чисел, аналогичные показанным на этом рисунке, могут представлять список телефонных вызовов в местной телефонной станции, или финансовую операцию между двумя счетами, либо любую ситуацию подобного рода, когда производится транзакция между двумя элементами предметной области, которым присвоены уникальные идентификаторы. Такие графы нельзя рассматривать как число случайные, ибо некоторые телефонные номера используются намного чаще, чем остальные, а некоторые счета характеризуются большей активностью, чем многие другие. Глава 17. Свойства и типы графов части 4, может быть приспособлен для решения этой задачи (см., например, программу 17.15). #include " ST.cc" template < class Graph> void IO< Graph>:: scan(Graph & G) { string v, w; ST st; while (cin» v» w) G.insert(Edge(st.index(v), st.index(w))); } Граф вызовов функций. Мы можем поставить граф в соответствие любой компьютерной программе, отождествляя функции с вершинами графа, при этом ребро соединяет вершину X с вершиной Y всякий раз, когда функция X вызывает функцию Y. Мы можем снабдить программу средствами построения таких графов (или заставить компилятор делать это). Для нас интерес представляют два абсолютно различных графа: статическая версия, когда мы строим ребра во время компиляции в соответствии с вызовами функций, которые появляются в программном тексте каждой функции; и динамическая версия, когда мы строим ребра во время выполнения программы, т.е. когда эти вызовы фактически происходят. Мы используем статические графы вызовов функций при изучении структуры программы и динамические графы при изучении поведения программы. Как правило, такие графы принимают большие размеры и относятся к категории разреженных. В приложениях, подобных рассматриваемым в этой книге, мы имеем дело с крупными массивами данных, так что довольно часто мы отдаем предпочтение изучению рабочих характеристик алгоритмов на реальных данных, а не на вероятностных моделях. Мы можем предпринять попытку избежать тупиковой ситуации за счет случайного выбора ребер или за счет введения в наши алгоритмы случайного фактора, который проявляется в процессе принятия решений, однако генерация случайных графов — это совсем другое дело. По существу, изучение свойств различных структур графов уже само по себе представляет несомненных интерес. Программа 17.15. Символьная индексация имен вершин________________________ Реализация индексации строковых ключей посредством таблицы символов (описание которой дано в пояснении к программе 17.14) завершает эту задачу добавлением поля index к каждому узлу TST-дерева (ternary search tree -дерево тернарного поиска) таблицы существования (см. программу 15.8). Индекс, ассоциированный с каждым ключом, хранится в поле индекса узла, соответствующего символу конца его строки. Как обычно, мы используем символы ключа поиска для перемещения по TST-дереву сверху вниз. Когда мы достигнем конца ключа, мы при необходимости устанавливаем значение его индекса, а также устанавливаем значение приватного элемента данных val, которое возвращается вызывающему объекту после того, как все рекурсивные обращения к рассматриваемой функции возвратят соответствующие значения. #include < string> class ST { int N, val; struct node { int v, d; node* 1, *m, *r; node(int d): v(-l), d(d), 1(0), m(0), r(0) {} }; Часть 5. Алгоритмы на графах typedef node* link; link head; link indexR(link h, const string & s, int w) { int i =s[w]; if (h == 0) h = new node(i); if (i == 0) { if (h-> v == -1) h-> v = N++; val = h-> v; return h; } if (i < h-> d) h-> l = indexR(h-> l, s, w); if (i == h-> d) h-> m = indexR(h-> m, s, w+1); if (i > h-> d) h-> r = indexR(h-> r, s, w); return h; } public: ST(): head(0), N(0) { } int index(const string & key) { head = indexR(head, key, 0); return val; } }; В нескольких таких примерах вершины представляют собой естественные имена объектов, а ребра выступают в виде пары именованных объектов. Например, граф транзакций может быть построен на базе последовательности пар телефонных номеров, а эвклидов граф — на базе последовательности пар городов или населенных пунктов. Программа 17.14 представляет собой реализацию функции scan из программы 17.14, которой мы можем воспользоваться для построения графов общей ситуации подобного рода. Для удобства клиентских программ она использует некоторое множество ребер в качестве определения графа и вычисляет множество имен вершин графа по мере того, как они появляются в ребрах. В частности, рассматриваемая программа считывает последовательность пар символов из стандартного ввода, использует таблицу символов для того, чтобы поставить в соответствие символам номера вершин в диапазоне от 0 до V - 1 (где V — число различных символов во вводе), и строит граф путем вставки ребер, как это имело место в программах 17.12 и 17.13. Мы можем приспособить реализацию, использующую таблицу символов, для поддержки средств, необходимых программе 17.14; программа 17.15 представляет собой пример использования TST-деревьев (см. главу 14). Эти программы существенно упрощают задачу тестирования разрабатываемых алгоритмов на реальных графах, которые, по всей видимости, не допускают точного представления с помощью какой бы то ни было вероятностной модели. Значение программы 17.15 велико еще потому, что она подтвердила наше предположение, которое мы допускали во всех разрабатываемых нами программах и которое заключается в том, что имена вершин являются целочисленными значениями в диапазоне от О до V— 1. Если в нашем распоряжении имеется граф с другим множеством имен вершин, то первым шагом в построении представления графа является выполнение программы 17.15, отображающей имена вершин на целые числа в диапазоне от 0 до V— 1. В основе некоторых графов лежат неявные связи между его элементами. Мы не будем рассматривать такие графы, однако подтвердим их существование несколькими следующими примерами и посвятим им несколько упражнений. Столкнувшись с задачей обработки такого графа, мы, естественно, можем написать программу построения явных Глава 17. Свойства и типы графов
графов путем нумерации всех его ребер, в то же время существуют задачи, решение которых не требует, чтобы мы нумеровали все ребра, благодаря чему время их выполнения подчиняется сублинейной зависимости. Граф со степенями разделения. Рассмотрим некоторую совокупность подмножеств из V элементов. Мы определяем граф таким образом: его вершина соответствует каждому элементу объединения подмножеств, а ребро между двумя вершинами проводится в том случае, если обе вершины встречаются в каком-то одном поднаборе (см. рис. 17.15). При желании этот граф может быть преобразован в мультиграф, в котором метки ребер именуют соответствующие подмножества. Говорят, что все элементы, инцидентные данному элементу v, отделены от вершины v одной степенью разделения {degree of separation). В противном случае все элементы, инцидентные какому-либо элементу, который отделен i степенями разделения от вершины v, (о которых еще не известно, сколькими степенями разделения они отделены от вершины v, / степенями или меньшим числом степеней разделения), обладают i + 1 степенями разделения с вершиной v. Такая конструкция служила развлечением для многих людей, от математиков (числа Эрдеша (Erdos)) до деятелей киноискусства (отделение от Кевина Бэкона (Kevin Bacon)). Интервальный граф. Рассмотрим совокупность V интервалов на действительной оси (пары вещественных чисел). Мы определяем граф следующим образом: каждому интервалу ставится в соответствие вершина, ребра между вершинами проводятся в том случае, когда соответствующие интервалы пересекаются (имеют любое число общих точек). РИСУНОК 17.15. ГРАФ СО СТЕПЕНЯМИ РАЗДЕЛЕНИЯ Граф в нижней части рисунка определяется группами, показанными в верхней части рисунка, при этом каждому имени соответствует вершина, а ребра соединяют вершины с именами, попадающими в одну и ту же группу. Кратчайшие длины пути в рассматриваемом графе соответствуют степеням разделения. Например, Франк отдален на три степени разделения от Алисы и Боба. Часть 5. Алгоритмы на графах
книге мы рассматриваем замысловатые алгоритмы, которые разрабатывались с целью решения практических задач, связанных со многими типами графов. На базе нескольких примеров, рассмотренных в данном разделе, мы приходим к заключению, что графы представляют собой сложные комбинаторные объекты, которые намного сложнее тех, что служат основой других алгоритмов, обсуждавшихся в главах 1-4. Во многих случаях графам, с которыми приходится иметь дело в приложениях, трудно или даже невозможно дать более-менее точную характеристику. Алгоритмы, которые хорошо показывают себя на случайных графах, часто не находят широкого применения ввиду того, что зачастую трудно убедиться в том, что случайные графы обладают теми же структурными характеристиками, что и графы, возникающие в приложениях. Обычный способ преодолеть это возражение предусматривает разработку алгоритмов, которые хорошо работают в наихудших случаях. И если этот подход приносит успех в одних случаях, он не оправдывает ожиданий в других (в силу своей консервативности). В то время как не всегда оправдываются наше предположение, что изучение рабочих характеристик на графах, построенных на базе одной из рассмотренных вероятностных моделей графа, даст нам достаточно точную информацию, которая обеспечила бы возможность прогнозировать производительность реальных графов, генераторы графов, которые мы рассматривали в данном разделе, полезны для тестирования реализаций исследуемых алгоритмов и понимания их сущности. Перед тем, как мы попытаемся спрогнозировать производительность приложения, мы, по меньшей мере, должны подтвердить правильность всех предположений, которые мы, возможно, сделали относительно отношений, связывающих данные приложения с какими бы то ни было моделями или образцами, которыми мы могли воспользоваться. И если такая проверка целесообразна при работе в любой области приложений, она особенно важна при обработке графов, что объясняется широким набором типов графов, с которыми приходится сталкиваться.
|