Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство по образованию Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
Нижегородский государственный университет им.Н.И.Лобачевского
Факультет вычислительной математики и кибернетики
Отчет по лабораторной работе
«Сравнение бесхитростного алгоритма и алгоритма Рэма с представлением разделенных множеств древовидной структурой»
Выполнил студент факультета
вычислительной математики и кибернетики
группы 8310 Демин Андрей
.
г.Н.Новгород
2013 г
Содержание
1.Введение
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико - графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры. Прямым применением теории связных графов является теория сетей — и её приложение — теория электронных сетей. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую, от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую).
Наиболее эффективными алгоритмами решения задачи о нахождении компонент связности являются бесхитростный алгоритм и алгоритм Рэма с представлением разделенных множеств древовидной структурой.
2.Постановка задачи
Задан неориентированный граф G = (V, E), имеющий n вершин и m ребер. Предполагаем, что граф задается двумерным массивом ребер E[1…m][1,2].
Требуется сравнить время и результаты работы бесхитростного алгоритма и алгоритма Рэма с представлением разделенных множеств древовидной структурой. Провести тестовые испытания для различного количества вершин и ребер и вывести сравнительные результаты в виде графиков.
3.Описание алгоритмов.
3.1. Бесхитростный алгоритм
Бесхитростный алгоритм похож на алгоритм Форда-Беллмана для задачи нахождения кратчайших расстояний. Решением данного алгоритма будет массив comp[1…n], где элемент comp[x] является номером (меткой) той компоненты связности, которой принадлежит вершина x. Сначала для любой вершины i полагается, что comp[i] = i, затем n-1 раз выполняются следующие действия: для любого ребра (i,j) значения comp[i] и comp[j] заменяются на min(comp[i],comp[j]).
Идея алгоритма Рэма состоит в том, чтобы представлять компоненты связности графа, содержащего текущее множество ребер, в виде структуры данных, называемой разделенными множествами. В данном варианте коллекция К (система разделенных множеств) представляется лесом, в котором каждое дерево соответствует некоторому подмножеству из К. В представлении деревьев узел ссылается на своего родителя, а корень сам на себя. Под именем подмножества здесь понимается корневой узел. Для этого вводится массив P[1..n] , где Р[i] = 0, если i ничему не принадлежит, Р[i] = родитель i, в противном случае. Также вводятся три операции с множествами:
Создаётся коллекция разделённых множества {1}, …, {n}. Далее последовательно обрабатываются все рёбра из E так, что при обработке очередного ребра (i,j) происходит объединение множества, содержащего i, и множества, содержащего j.
4.Обоснование теоретических оценок временной сложности алгоритмов.
Бесхитростный алгоритм имеет оценку сложности O(nm). Сначала для каждой вершины i полагается, что comp[i]=i, т.е. n итераций. Основной цикл выполняется n - 1 раз, в каждом из них для каждого ребра(m) проводится операция: comp[i] = comp[j] = min(comp[i], comp[j]). Таким образом, общая оценка сложности алгоритма O(nm).
Временная сложность алгоритма Рэма есть O(nm). Основной цикл алгоритма Рэма выполняется m раз, на каждой итерации производится поиск двух вершин в коллекции со сложностью O(hx), где hx – высота от искомой вершины до корневого узла и слияние двух множеств О(1) (т.к. это прямое обращение по индексу). Тогда общая сложность алгоритма O(nm).
5.Описание реализующих алгоритмы программ
Для достижения поставленной цели потребовалось реализовать бесхитростный алгоритм и алгоритм Рэма в среде Microsoft Visual Studio.. В результате при помощи созданной программы была получена возможность выделения компонент связности графа, при случайном распределении ребер, при ручном вводе и вводе при помощи файла.
Программа Lab A,B состоит из меню с пятью пунктами:
1)Генерация случайного графа с заданными параметрами, и получение времени работы алгоритмов. Результат также записывается в файл rez.txt.
Пункты 2,3,4,5 предназначены для проведения экспериментов, результатом которых является время работы алгоритмов.
Используемые функции:
reb(int n, int &x1 ,int &y1)– создает случайное ребро .
graf( int **e,int n,int m) - процедура создания случайного графа G(n,m) с заданными параметрами.
rebrplus( int **e,int n,int m) ) - процедура добавления случайного ребра.
sozd(int *p,int i) )– создание синглетона {i}.
obed(int *p, int i,int j) объединение множества коллекции K с именами i и j.
search(int *p,int x) найти имя множества коллекции K, содержащее элемент x.
bezhitr(int*comp,int**e,int n,int m) реализует бесхитростный алгоритм.
void bezhitr(int*comp,int**e,int n,int m)
{
for (int i=0; i<n; i++)
comp[i]=i;
int q=0;
for (int i=0; i<n-1; i++)
for (int j=0; j<m; j++)
{
q=min( comp[e[j][0]], comp[e[j][1]]);
comp[e[j][0]]=q;
comp[e[j][1]]=q;
}
}
rem(int *comp,int**e,int n,int m) реализует алгоритм Рэма.
void rem(int *comp,int**e,int n,int m)
{
int n1,n2;
for (int i=0; i<n; i++)
sozd(p,i);
for (int j=0; j<m; j++)
{
n1=search(p,e[j][0]);
n2=search(p,e[j][1]);
if(n1!=n2)
obed(p,n1,n2);
}
for (int i=0; i<n; i++)
{
comp[i]=search(p,i);
}
}
6. Проведенные эксперименты
Проанализирована работа бесхитростного алгоритма и алгоритма Рэма, после чего составлены графики тестирования скорости работы, по которым можно сравнить работу алгоритмов.
Эксперимент 1. n=1…1001 с шагом 10, m=[n2/10]
Сравнительный график:
Эксперимент 2. n=1…1001 с шагом 10, m=n-1
Сравнительный график:
Эксперимент 3. n=1…10001 с шагом 100, m =[log2(n)]
Сравнительный график:
Эксперимент 4. n=1…1001 с шагом 10, для каждого n на вход алгоритма Рэма подавать случайную последовательность неповторяющихся ребер до тех пор, пока граф не станет связным.
График является немонотонным, так как ребра генерируются случайно, поэтому количество ребер в графе превосходит минимальное количество ребер, которое необходимо для связности графа (n-1, где n – количество ребер).
Нарисованная зависимость числа ребер от числа вершин приближенно может быть выражена прямой: m=α*n, где α=3.
7. Сравнение алгоритмов
Немонотонный характер графиков обусловлен случайной генерацией ребер графов. Для многих случаев, время на графике равно 0. На самом деле время выполнения всегда отлично от 0, но точность с которой, мы можем замерять время ограничена(ограничение порядка 1 миллисекунды).
Несмотря на влияние случайных воздействий, можно отметить превосходство алгоритма Рэма над бесхитростным алгоритмом при количестве ребер сравнимом с количеством вершин, которое при увеличении количества ребер возрастастает.
8.Выводы
При количестве ребер много меньшем количества вершин (сильно разреженные графы) оба алгоритма работают со сравнимой эффективностью.
Алгоритм Рэма безусловно превосходит бесхитростный алгоритм на большом количестве ребер и может быть применен в большинстве задач, связанных с отысканием компонент связности.