Читать курсовая по всему другому: "Алгоритмы поиска остовного дерева Прима и Крускала" Страница 1

(Назад) (Cкачать работу)

Министерство образования и науки Украины

Сумский государственный университет

Кафедра Информатики Курсовая работа

по дисциплине

“Теория алгоритмов и математическая логика”

на тему:

“Алгоритмы поиска остовного дерева Прима и Крускала” Сумы 2006

СодержаниеЗадание

Вступление

1. Теоретическая часть

2. Практическая реализация

Вывод

Программный код

Литература Задание Разработать программную реализацию решения задачи о минимальном покрывающем дереве (построение минимального остова). Для нахождения минимального покрывающего дерева использовать алгоритмы Прима и Крускала.Исходная информация о ребрах графа находится в текстовом файле dan.txt. ВступлениеПусть имеется связный неориентированный граф G = (V, Е), в котором V - множество контактов, а E - множество их возможных попарных соединений. Для каждого ребра графа (u, v) задан вес w(u, v) (длина провода, необходимого для соединения u и v). Задача состоит в нахождении подмножества ТЕ, связывающего все вершины, для которого суммарный вес минимален.

w(T) = w(u,v)

Такое подмножество Т будет деревом (поскольку не имеет циклов: в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа. (Иногда используют термин "остовное дерево"; для краткости мы будем говорить просто "остов".)

Далее мы рассмотрим задачу о минимальном покрывающем дереве. (Здесь слово "минимальное" означает "имеющее минимально возможный вес".)

Рис 1На Рис 1 показано на примере минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены ребра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (Ь, с) ребром (а,h), получаем другое дерево того же веса 37.

Мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать со временем работы O(E logV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до O(E+V logV) (что меньше Е logV, если |V| много меньше \Е\).

Оба алгоритма следуют "жадной" стратегии: на каждом шаге выбирается "локально наилучший" вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так. Здесь будет описана общая схема алгоритма построения минимального остова (добавление рёбер одного за другим). В дальнейшем будут указаны две конкретных реализации общей схемы.

Итак, пусть дан связный неориентированный граф G = (V, Е) и весовая функция w: Е. Мы хотим найти минимальное покрывающее дерево (остов), следуя жадной стратегии.

Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого минимального остова. Ребро (u, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: А{(u, v)} тоже должно быть подмножеством минимального остова. Мы называем такое ребро безопасным ребром для А.

Generic-MST(G,w)

1 А

2 while A не является остовом

3 do найти безопасное ребро (u,v) для А

4 АA{(u,v)}

5 return A

Рис. 2. Два

Похожие работы