Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 18. Поиск на графе. просматривает каждый элемент матрицы, вследствие чего время его выполнения оказывается пропорциональным размеру (V2) матрицы
|
|
просматривает каждый элемент матрицы, вследствие чего время его выполнения оказывается пропорциональным размеру (V2) матрицы, а не числу единиц в ней (Е). Из таблицы следует, например, что на обработку графа, содержащего 1000 ребер, затрачивается примерно такое же время, которое требуется на обработку графа, содержащего 100000 ребер в случае использования матрицы смежности.
Во-вторых, из таблицы 18.2 легко видеть, что затраты на распределение памяти под узлы списков достигают больших значений, когда списки смежных вершин строятся для крупных разреженных графов. Затраты на построение таких списков превосходят стоимость их обхода более чем в пять раз. В типичной ситуации, когда есть намерения выполнить многочисленные поиски различных типов после того, как граф будет построен, цена становится приемлемой. В противном случае мы должны рассмотреть альтернативные реализации, позволяющие снизить эти затраты.
В третьих, отсутствие числовых значений в столбцах DFS для крупных разреженных графов весьма существенно. Такие графы порождают избыточную глубину рекурсии, которая (в конечном итоге) приводит к аварийному завершению программы. Если для таких графов мы хотим использовать поиск в глубину, необходимо применять нерекурсивные версии программ, о чем шла речь в разделе 18.7.
В-четвертых, эта таблица показывает, что метод, в основу которого положен алгоритм объединения-поиска, описанный в главе 1, обладает большим быстродействием, чем поиски в глубину и в ширину, главным образом за счет того, что для него не требуется представление графа целиком. Однако, не имея такого представления, мы не можем дать ответ на такие простые запросы, как: " существует ли ребро, соединяющее вершины v и w? ". Таким образом, методы, основанные на алгоритме объединения-поиска, не подходят, если мы хотим получить от них нечто большее, на что они способны (в частности, ответы на запросы типа " существует ли ребро, соединяющее вершины v и w? " вперемешку с добавлением ребер). Если внутреннее представление графа построено, нецелесообразно строить алгоритм объединения-поиска только для того, чтобы узнать, связный граф или нет, поскольку и поиск в глубину, и поиск в ширину могут дать ответ так же быстро.
Когда мы проводим эмпирические испытания, которые приводят к появлению подобного рода таблиц, различные аномальные явления могут потребовать дальнейших пояснений. Например, на многих компьютерах архитектура кэш-памяти и другие свойства запоминающего устройства могут решающим образом повлиять на производительность алгоритма на крупных графах. Необходимость повышения производительности критических приложений может потребовать, помимо всех факторов, которые мы сейчас рассматриваем, и самого подробного изучения архитектуры машины.
Подробное исследование этих таблиц позволяет обнаружить больше свойств этих алгоритмов, чем мы способны изучить. Однако наша цель состоит не в том, чтобы провести тщательное сравнение, но и показать, что несмотря на множество проблем, с которыми приходится сталкиваться при сравнении различных алгоритмов на графах, мы можем и должны проводить эмпирические исследования и извлекать пользу из любых аналитических результатов как с целью получить представление об основных особенностях алгоритмов, так и с целью прогнозирования их производительности.
Часть 5. Алгоритмы на графах
Упражнения
о 18.72. Выполните эмпирические исследования, основной целью которых должно быть получение таблицы, подобной таблице 18.2, для задачи, определяющей, является ли заданный граф двухдольным (допускает ли раскрашивание в два цвета).
18.73. Выполните эмпирические исследования, основная цель которых состоит в том, чтобы получить таблицу, подобную таблице 18.2, для задачи, определяющей, является ли заданный граф двусвязным.
о 18, 74. Выполните эмпирические исследования с целью определить размер второй по величине связной компоненты разреженных графов различных размеров, построенных на базе различных моделей (упражнения 17.64—17.76).
18.75. Напишите программу, которая способна строить диаграммы, подобные показанной на рис. 18.30, и протестируйте ее на графах различных размеров, в основе которых лежат различные модели (упражнения 17.64-17.76).
о 18.76. Внесите изменения в программу из упражнения 18.75 с целью построения аналогичных гистограмм размеров реберно-связных компонент.
•• 18.77.Числа в таблицах, приведенных в данном разделе, получены при исследовании только одного образца. Возможно, мы захотим подготовить аналогичную таблицу, для получения одного элемента которой мы готовы провести 1000 экспериментов и получить выборочное среднее и среднее отклонение, но, по-видимому, мы не сможем включить примерно такое число элементов. Гарантирует ли данный подход более эффективное использование времени компьютера? Дайте обоснование своего ответа.
