Министерство образования РФ
Нижегородский государственный университет имени
Факультет ВМК
Лабораторная работа № 1.2
«Нахождение кратчайших путей в графе»
Выполнил:
группа № 86М2,
Проверил:
Н. Новгород
2008 г.
Оглавление
Оглавление. 2
Описание алгоритмов. 3
Описание структур данных. 3
Алгоритм Дейкстры, реализованный на основе Д-кучи. 3
Обоснование теоретической оценки временной сложности алгоритмов. 5
Алгоритм Дейкстры, реализованный на основе Д-кучи. 5
Описание реализующих алгоритмы программ.. 6
Проведенные эксперименты.. 7
Сравнение алгоритмов. 15
Выводы.. 16
Описание алгоритмов
Описание структур данных
В данной лабораторной работе рассматривается задача нахождения кратчайших путей в ориентированном графе без петель и кратных ребер. Соответственно основной структурой данных является граф, который представлен как массив списков смежности (окрестностей) своих вершин. При этом в окрестности хранятся структуры с номерами вершин, в которые идут ориентированные ребра. Каждая структура хранит номер вершины, оканчивающей ребро, вес идущего в нее ребра, признак принадлежности вершины графу и указатель на следующую вершину в окрестности. Окончанием окрестности является нулевая ссылка.
В алгоритмах используется также приоритетная очередь на основе Д-кучи. Д-куча представлена как три массива: массив имен вершин, массив ключей вершин (где ключ вершины – это оценка кратчайшего расстояния от исходной вершины до данной) и массив индексов вершин (то есть номеров вершин в приоритетной очереди). Приоритетная очередь на основе Д-кучи строится так: Д-куча представляется как корневое дерево, где корень находится на наивысшем уровне. Корнем является вершина с наименьшим ключом. Каждая вершина (не лист), кроме, возможно, одной имеют ровно Д потомков. Ключ каждого потомка вершины не меньше ключа самой вершины. Таким образом, высота Д-кучи равна [logdn]. С Д-кучей осуществляются следующие операции: всплытие вершины (вершина с ключом, меньшим, чем у родителя, поднимается наверх, пока не займет соответствующее ее ключу положение), погружение вершины (вершина с ключом, большим, чем у потомка, опускается вниз, пока не займет соответствующее ее ключу положение), изъятие минимума (выбор и удаление вершины с наименьшим ключом), образование приоритетной очереди. Для каждой вершины Д-кучи можно определить ее первого, последнего и минимального потомка и родителя.
В данной лабораторной работе рассматриваются два алгоритма: алгоритм Дейкстры, основанный на использовании 3-кучи и алгоритм Дейкстры, основанный на использовании 4-кучи. Оба алгоритма возвращают два массива значений: массив расстояний от исходной вершины до всех остальных и массив «отцов» (последних вершин на пути от исходной). Т. к. алгоритмы различаются только значением числа Д, а в остальном они одинаковы, рассмотрим общую схему их работы.
Алгоритм Дейкстры, реализованный на основе Д-кучи
В данном алгоритме сначала происходит создание Д-кучи, а затем инициализация массивов, хранящих Д-кучу и предварительная инициализация возвращаемых массивов. Массив «отцов» инициализируется нулями, массивы расстояний и ключей в Д-куче инициализируются неким «большим» значением (это значение должно быть больше длины любого пути в графе), массивы имен и индексов в Д-куче инициализируются последовательно натуральными числами от 1 до количества вершин в графе. Ключ исходной вершины устанавливается как ноль. Далее на основе Д-кучи организуется приоритетная очередь.
Пока приоритетная очередь не исчерпана, выполняются следующие действия: извлекается минимум, расстояние до данной вершины устанавливается равным ее ключу, далее выполняется просмотр всей окрестности этой вершины. В ходе просмотра окрестности, пока не достигнут конец окрестности, для каждой вершины выполняются следующие действия: сравнивается ключ текущей вершины с суммой расстояния от исходной вершины до вершины-родителя и веса ребра из вершины-родителя в текущую вершину. Если ключ больше, то он устанавливается равным данной сумме, затем происходит всплытие текущей вершины в приоритетной очереди, «отцом» текущей вершины устанавливается вершина-родитель.
Обоснование теоретической оценки временной сложности алгоритмов
Алгоритм Дейкстры, реализованный на основе Д-кучи
Теорема:
Временная сложность алгоритма Дейкстры, реализованного на основе Д-кучи (Д является константой, не меньшей 2), оценивается сверху величиной O((d*n+m)×logdn), где n - число вершин, m - число ребер.
Доказательство:
Рассмотрим сначала временную сложность алгоритмов, производимых с Д-кучей. Очевидно, что при реализации Д-кучи в виде трех массивов, временная сложность таких операций, как определить первого, последнего потомков и отца вершины, будет О(1). Определение минимального потомка осуществляется за время О(d), так как происходит в общем случае не более d сравнений. Всплытие осуществляется за время О(logdn), так как происходит не более чем logdn сравнений и обменов. Погружение осуществляется за время О(dlogdn), так как происходит не более logdn обменов, при каждом из которых выполняется ровно d сравнений. Операция «изъятие минимума» сводится к одному погружению, соответственно и временная сложность ее такая же. Организация приоритетной очереди на основе Д-кучи осуществляется за время О(n). Докажем это. Заметим, что трудоемкость погружения с высоты h равна O(h), а количество узлов высоты h не превосходит целой части от n/dh +1(это несложно доказать по индукции: на наивысшем уровне только один узел, на каждом последующем не более чем в d раз больше; под высотой узла понимается расстояние от него до наиболее далекого потомка). Осталось оценить сумму
где H=[logdn]+1, и убедиться, что полученная сумма есть O(n).
=
=(воспользуемся формулой 
=
)=
=О(n).
Теперь доказательство оценки временной сложности алгоритма: в ходе этого алгоритма выполняются следующие действия: инициализация пяти массивов длиной n (время пропорционально 5n), организация приоритетной очереди (время пропорционально n), n изъятий минимума (время пропорционально dlogdn) и не более m всплытий (время пропорционально logdn). «Изъятий минимума» ровно n, так как просматривается вся очередь, и всплытий не более m, так как вершина может «опускаться» не с каждым ребром. Итого затрачивается времени 6n+ndlogdn+mlogdn, то есть О((d*n+m)* logdn). Доказательство теоремы закончено.
Описание реализующих алгоритмы программ
Структуры данных «граф», «окрестность», «Д-куча» реализованы в данной программе как классы, структура данных «вершина графа» реализована как структура. Сами структуры подробно описаны в главе «Описание алгоритмов». В класс «Граф» добавлены также два числовых поля – минимальная и максимальная границы веса ребра. Процедура, реализующая алгоритм, содержатся в классе «Граф». Таким образом, временные структуры данных, которые используются только в данных алгоритмах (Д-куча и массив меток), создаются и освобождаются непосредственно в ходе соответствующих процедур. На это тратится лишнее время, не занятое полезными вычислениями.
Программы написаны на языке С++ в среде программирования Borland C++ Builder 5.0. Каждая структура данных хранится в отдельном модуле, кроме того, для каждой программы существует модуль, описывающий основную форму и связанные с ней действия.
Интерфейс программ прост и интуитивно понятен. Более подробную информацию о программах и работе с ними можно узнать в прилагающихся к ним инструкциях.
Проведенные эксперименты
В данной лабораторной работе проведены семь серий экспериментов. В каждой серии один из параметров изменяется от одного определенного значения до другого с определенным шагом. Результаты работы алгоритмов в ходе обработки каждой серии представлены на соответствующих графиках. На данных графиках по оси Х отложены значения изменяющегося параметра, а по оси Y время в секундах. Для наглядности графики работы обоих алгоритмов нарисованы в одной системе координат, при этом красная ломаная соответствует алгоритму Дейкстры, использующему 3-кучу, синяя – алгоритму Дейкстры, использующему 4-кучу. В обозначениях серии используются следующие условные обозначения: n – число вершин графа, m – число ребер графа, r – верхняя граница веса ребра, q – нижняя граница веса ребра.
Итак, рассмотрим проведенные эксперименты:
1) n = 1,...,1001 с шагом 10, q = 1, r = 106, m = n2/10
2) n = 1,...,1001 с шагом 10, q = 1, r = 106, m = n2
3) n = 101,...,3001 с шагом 30, q = 1, r = 106, m = 100*n
4) n = 101,...,3001 с шагом 30, q = 1, r = 106, m = 1000*n
5) n = 3001, m = 0,...,900’000 с шагом 10’000, q = 1, r = 106
6) n = 1000, q = 1, r = 1,...,200 с шагом 1, m = n2
7) n = 500, q = 1, r = 1,...,200 с шагом 1, m = 100*n
Сравнение алгоритмов
Как мы можем видеть на основании графиков, алгоритм Дейкстры, использующий 4-кучу, работает быстрее, чем алгоритм, использующий 3-кучу, во всех сериях в подавляющем большинстве случаев (за исключением некоторых отдельных частных экспериментов).
Следует отметить тот факт, что, согласно экспериментам, ширина диапазон веса ребра не влияет на время работы алгоритма (независимо от количества вершин и ребер).
Полученные графики являются достаточно гладкими, однако при этом в них иногда встречаются неожиданные относительно узкие всплески («пики»), которые, скорее всего, являются следствием «помех» от фоновых процессов операционной системы.
Выводы
Из приведенного сравнения алгоритмов можно сделать следующие выводы:
1. алгоритм Дейкстры, использующий 4-кучи в большинстве случаев быстрее, чем алгоритм, использующий 3-кучу;
2. т. к. полученная нами оценка является верхней, но не асимптотической, и получение асимптотической оценки не представляется возможным, вывод о соответствии теории и практики сделаем на основании следующих рассуждений:
· каждый график соотнесем с некоторой стандартной функцией имеющей график похожего вида; несложно заметить, что графики 1 и 2 напоминают параболу (Q(n2)), 3 и 4 – линейную функцию (Q(n)), 5 – линейную функцию (Q(m)), 6 и 7 – константу (Q(1));
· в случаях 1 и 2 m=c*n2; таким образом, верхнюю оценку можно переписать в виде O(n2*logdn), причем данная функция асимптотически больше, чем функция Q(n2);
· в случаях 3 и 4 m=c*n; таким образом, верхнюю оценку можно переписать в виде O(n*logdn), причем данная функция асимптотически больше, чем функция Q(n);
· в случае 5 m=c*n; таким образом, верхнюю оценку можно переписать в виде O(m) (т. к. параметром серии экспериментов является число ребер), причем данная функция асимптотически не меньшее функции Q(m);
· в случаях 6 и 7 графики (с учетом незначительных колебаний) являются константными, что говорит о том, что время работы алгоритмов не зависит от ширины диапазона весов ребер, а также от значений верхней и нижней границы этого диапазона.
На основании всего вышеизложенного мы видим, что практические результаты во всех случаях асимптотически не превосходят полученную нами верхнюю оценку. Таким образом, можно сделать вывод о том, что практика соответствует полученным теоретическим результатам.
