Описание работы с программой.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАТИКИ И РОБОТОТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
Курсовая работа по дисциплине
Дискретная математика
«Алгоритм Борувки - Соллина»
Выполнил:
Студент группы ПРО-201 Исмагилов А.З.
Проверила:
Доцент кафедры ВМК Усманова А. Р.
УФА 2012.
Оглавление
Оглавление
Оглавление. 2
Введение. 3
Теоретическая часть. 3
Постановка задачи. 3
Описание алгоритма. 4
Реализация. 4
Описание работы с программой. 6
Пример выполнения программы: 6
Выводы.. 8
Список литературы: 8
Введение
Теория графов – крупный раздел Дискретной математики и, как следствие – информатики и программирования. Причем теория графов имеет довольно обширное применение: навигационные системы, системы планировки, оптимизации – все они подразумевают использования графов. Также стоит отметить, что использование минимальных остовных деревьев значительно расширяют возможности графов для более оптимального решения задач.
Множество алгоритмов можно придумывать самому, но более продуктивнее использовать уже готовые. И мне представилась возможность поработать с менее известным, но одним из первых алгоритмов для на нахождения минимального остовного дерева – алгоритмом Борувки - Соллина.
|
|
|
Теоретическая часть.
Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.
Остовный лес – любой ациклический подграф, в который входят все вершины графа, но не обязательно связный.
Компонента связности – максимальный набор вершин графа, для которого существует путь между каждой парой вершин.
Остовное дерево (spanning tree)графа G = (V,E) –подмножество ребер множества E, которые создают дерево, содержащее все вершины V.
Минимальное остовное дерево(minimal spanning tree) — остовные деревья с минимальной суммой весов ребер.
Алгоритм Борувки — Соллина — алгоритм нахождения минимального остовного дерева в графе. Впервые был опубликован в 1926 году в качестве метода нахождения оптимальной электрической сети в Моравии. Был переоткрыт Соллином, который был западным ученым и поэтому алгоритм часто называют алгоритмом Соллина. Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении ребер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть лес состоящий из одной компоненты связности.
|
|
|
Динамическое программирование— способ решения сложных задач путём разбиения их на более простые подзадачи.
Постановка задачи
Написать программу, которая находила бы минимальное остовное дерево в заданном графе при помощи алгоритма Борувки-Соллина, выводила бы полученную матрицу, а так же реализовывала возможность вывода полученного минимального остовного дерева.
Описание алгоритма
1. Изначально, пусть T – пустое множество ребер( представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
2. Пока T не является деревом( что эквивалентно условию: пока число ребёр в T меньше, чем V – 1, где V – число вершин в графе):
|
|
|
· Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами T, найдем самое дешёвое ребро связывающее эту компоненту с некоторой другой компонентой связности. (Предпологается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
· Добавим все найденные ребра в множество T.
3. Полученное множество рёбер T является минимальным остовным деревом входного графа.
Алгоритм совершает не более O(log V) итераций. Каждая итерация может быть реализована со сложностью O(E), поэтому общее время работы алгоритма составляет O( ELogV) времени (здесь V и E – число вершин и рёбер в графе соответственно).
Реализация
Алгоритм Борувки- Соллина
QVector<int> t;
int MAXV = 100;
int mas[MAXV+1][MAXV+1];
int minEdge[MAXV+1];
int n = 0;
for(int i=0;i<MAXV;++i)
for(int j=0;j<MAXV;++j)
mas[i][j] = 0;
// Заполнение массива mas весами ребер
for(int i=0;i<scene->count;++i)
{
for(int j=0;j<scene->count;++j)
{
if(ui->tableWidget->item(i,j) != 0)
{
mas[i][n] = ui->tableWidget->item(i,j)->text().toInt();
n++;
}
}
}
//алгоритм
while(t.size() < scene->count - 1)
{
int k = 0;
while(k != scene->count)
{
for(int j=0;j<MAXV;++j)
|
|
|
if(mas[k][j] != 0)
{
if(mas[k][j] < mas[k][j+1])
minEdge[k] = mas[k][j];
else minEdge[k] = mas[k][j+1];
k++;
}
}
for(int i=0;i<scene->count;++i)
t.push_back(minEdge[i]);
scene->update();
}
Вывод минимального остовного дерева:
for(int i=0;i<scene->count;++i)
{
for(int j=0;j<scene->count;++j)
{
if(ui->tableWidget->item(i,j) != 0)
{
if(minEdge[i] == ui->tableWidget->
item(i,j)->text().toInt())
{
scene->addLine(scene->vertex[i].x()+12,
scene->vertex[i].y()+12,
scene->vertex[j].x()+12,
scene->vertex[j].y()+12);
int p = (scene->vertex[i].x()+scene->vertex[j].x())/2;
int l = (scene->vertex[i].y()+scene->vertex[j].y())/2;
QGraphicsTextItem * io = new QGraphicsTextItem;
io->setPos(p-20,l-20);
io->setPlainText(QString::number(minEdge[i]));
scene->addItem(io);
}
}
}
}
Описание работы с программой.
Оболочка программы выглядит следующим образом:
В поле, что находится сверху матрицы смежности вводится сам граф. Левый щелчок мышки создает новую вершину. В матрицу смежности вводятся весы ребер соответствующей связной компоненте. Затем нажимается кнопка «Расчитать» и выводится само минимальное остовное дерево. Кнопка «Очистить» удаляет все содержимое в матрице смежности и сам граф.
Пример выполнения программы:
Исходный граф:
Результат выполнения нахождения минимального остовного дерева:
Матрица смежности:
Выводы
Полученная программа удовлетворяет поставленным условиям задачи. Конечно же, программа нуждается во многих доработках. Прежде всего в доработке нуждается оболочка. Тем не менее, с программой вполне можно работать, в ней не трудно разобраться, и она довольно стабильна. Для решения аналогичной задачи можно использовать алгоритм Прима и многие другие, однако главный плюс алгоритм Борувки - Соллина – его простота и легкость в реализации.
Данная программа имеет довольно обширное применение. Её можно модернизировать для более разнообразной работы с графами – поиск обхода в глубину, в ширину, а так же применить иные алгоритмы нахождения минимальных остовных деревьев (Например, алгоритм Крускала). Конкретно данную программу можно также использовать в Дискретной математике, для нахождения минимального остовного дерева в графе.
Список литературы:
1. Усманова А. Р. – Конспекты лекций по Дискретной Математике.
2. http://ru.wikipedia.org/wiki/
3. Стивен Скиена – Алгоритмы. Руководство к разработке. 2 – е изд.: Пер. с англ.- Спб.: БХВ-Петербург, 2011.
4. Карамова Л. М. – Конспекты лекций по Программированию.
5. Верхотурова Г.Н. – Конспекты лекций по Алгоритмам и Структурам Данных.
Дата добавления: 2018-08-06; просмотров: 226; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!