Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17. Свойства и типы графов. тур данных с многочисленными неравноценными компонентами и в самом деле представляет собой трудную задачу.
|
|
тур данных с многочисленными неравноценными компонентами и в самом деле представляет собой трудную задачу.
Мы можем также рассмотреть и альтернативные реализации, которые выполняют модификацию базовых структур данных в процессе настройки рабочих характеристик с целью экономии пространства памяти или времени выполнения при обработке крупных графов (или большого числа графов небольших размеров). Например, мы можем существенно повысить производительность алгоритмов, выполняющих обработку крупных статических графов, представленных списками смежных вершин, отказавшись от представления множества вершин, инцидентных каждой конкретной вершине, в виде связных списков и воспользовавшись их представлением в виде векторов переменной длины. Пользуясь такой технологией, мы можем в конечном итоге представить граф всего лишь 2Е целыми числами, что меньше V, и V целыми числами, что меньше V2 (см. упражнения 17.52 и 17.54). Подобные представления особенно привлекательны в условиях обработки крупных статических графов.
Алгоритмы, которые мы рассматриваем, легко приспосабливаются ко всем изменениям, предложенным нами в этом разделе, поскольку в их основу положены несколько высокоуровневых операций, таких как " выполнить следующую операцию на каждом ребре, связанном с вершиной v", которые поддерживаются построенным базовым АТД.
В некоторых случаях наши решения относительно структуры алгоритма зависят от некоторых свойств конкретного представления графа. Работа на высоком уровне может отодвинуть на задний план наше осознание этой зависимости. Если мы знаем, что одно представление ведет к снижению производительности алгоритма, а другое нет, мы берем на себя неоправданный риск, если будем планировать применение алгоритма на неправильно выбранном уровне абстракции. Как обычно, наша цель состоит в том, чтобы построить такие реализации, которые позволяли бы давать точную оценку производительности алгоритма. По этой причине мы сохраняем отдельные типы DenseGRAPH (насыщенный граф) и SparseMultiGRAPH (разреженный мультиграф) для представления графа, соответственно, в виде матрицы смежности и в виде списка смежных вершин с тем, чтобы клиенты могли воспользоваться той из реализаций, которая лучше подходит для решения стоящей перед ними задачи.
В худшем случае простой алгоритм выбора пути, описанный в разделе 17.7, (а также несколько других методов, которые мы будем изучать в граве 18) исследует все Е ребер графа. Вхождения в среднем и правом столбцах нижней строки таблицы 17.1 показывают, соответственно, что этот алгоритм может проверить все V1 вхождений представления графа в виде матрицы смежности и все V заголовков списков и все Е узлов в списках в представлении графа в виде списков смежных вершин. Из этого следует, что время счета алгоритма линейно зависит от размера представления графа, в то же время имеются два исключения из этого правила: в худшем случае линейная зависимость времени счета от числа ребер графа нарушается, если мы используем матрицу смежности для представления разреженного графа или для представления очень разреженного графа (граф, который содержит большое число изолированных вершин). Чтобы больше не останавливаться на этих исключениях, в дальнейшем мы полагаем, что размер представления графа, которое мы используем, пропорционален числу ребер этого графа. В большинстве практических приложений эта гипотеза подлежит дальнейшим исследованиям, поскольку они производят
Часть 5. Алгоритмы на графах
обработку крупных разреженных графов и, следовательно, отдают предпочтение представлению графа в виде списков смежных вершин.
Значение в нижней строке левого столбца таблицы 17.1 получено по результатам применения алгоритмов объединения-поиска, описанного в главе 1 (см. упражнение 17.15). Этот метод привлекателен тем, что требует пространство памяти, всего лишь пропорциональное числу вершин V графа, однако его недостаток заключается в том, что он не способен показывать пути. Это вхождение в таблицу 17.1 подчеркивает важность полного и точного описания задач обработки графов.
Даже после того, как все эти факторы будут учтены, одной из наиболее важных и трудных проблем, с которыми нам приходится сталкиваться при разработке практических алгоритмов обработки графов, является оценка того, насколько рабочие характеристики этих алгоритмов, полученные для худших случаев наподобие представленных в таблице 17.1, переоценивают потребности во времени и в пространстве памяти обработки графов, которые встречаются на практике. Большая часть публикаций по алгоритмам на графах описывает рабочие характеристики в переводе на показатели, которые гарантируются в худшем случае, и в то время как эта информация полезна при выявлении алгоритмов, которые могут обладать заведомо неприемлемыми характеристиками, она может оказаться не в состоянии пролить свет на то, какая из нескольких простых программ является наиболее подходящей для заданного применения. Эта ситуация усугубляется трудностями разработки полезных рабочих моделей алгоритмов на графах для обычных условий работы; все что нам остается (возможно, это ненадежный метод) — это проверка в контрольных точках и (возможно, это чрезмерно консервативный метод) характеристик, гарантированных в худшем случае, на которые мы можем опираться на практике. Например, все методы поиска на графах, которые рассматриваются в главе 18, представляют собой эффективные алгоритмы, подчиняющиеся линейной зависимости и предназначенные для поиска пути между двумя заданными вершинами, однако их рабочие характеристики существенно различаются в зависимости от того, какой граф подвергается обработке и как он представлен. При использовании алгоритмов обработки графов на практике мы ведем постоянную борьбу с таким несоответствием гарантированных рабочих характеристик в худшем случае, которые мы можем доказать, и фактических рабочих характеристик, которые мы имеем основания ожидать. С этой темой мы будем периодически соприкасаться на протяжении всей этой книги.