Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала - Математика курсовая работа
Главная
Математика
Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала
Особливості реалізації алгоритмів Прима та Крускала побудови остового дерева у графі. Оцінка швидкодії реалізованого варіанта алгоритму. Характеристика різних методів побудови остовних дерев мінімальної вартості. Порівняння використовуваних алгоритмів.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Міністерство освіти і науки України
«Теорія алгоритмів та математична логіка»
«Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала»
При виконанні ОДЗ необхідно реалізувати алгоритми Прима та Крускала побудови остового дерева у графі, та протестувати її на тестовому графі наведеному у завданнях до ОДЗ згідно вашого варіанту. У пояснювальній записці до ОДЗ повинно бути викладено наступне:
* Вступ. Короткі відомості про поняття остового дерева;
* Завдання роботи, Включаючи тестовий приклад графу, згідно варіанта;
? короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування (10%);
? остове дерево, отримане за допомогою алгоритму (5%);
? фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);
? оцінку швидкодії реалізованого варіанта алгоритму (10%).
? короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування(10%);
? остове дерево, отримане за допомогою алгоритму (5%);
? фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);
? оцінку швидкодії реалізованого варіанта алгоритму (10%).
* Порівняння алгортимів, контрольні приклади:
? висновок що до умов, коли доцільно використовувати той чи інший алгоритм (10%)
? довільний граф (10 або більше вершин), на якому алгоритм Прима дає перевагу, навести фактичні параметри швидкодії (10%);
? довільний граф (10 або більше вершин), на якому алгоритм Крускала дає перевагу, навести фактичні параметри швидкодії (10%).
Поставлене завдання: маючи на вході граф G, одержати на виході його остовне дерево мінімальної вартості, використати алгоритми Крускала й Прима. Порівняти використовувані алгоритми.
Нехай G = (V, Е) -- зв'язний граф, у якому кожне ребро (u,v ) позначено числом c(u, v), що називається вартістю ребра. Остовним деревом графа G називається вільне дерево, що містить всі вершини V графа G. Вартість остовного дерева обчислюється як сума вартостей всіх ребер, що входять у це дерево.
Типове застосування остовних дерев мінімальної вартості можна знайти при розробці комунікаційних мереж. Тут вершини графа представляють міста, ребра - можливі комунікаційні лінії між містами, а вартість ребер відповідає вартості комунікаційних ліній. У цьому випадку остовне дерево мінімальної вартості представляє комунікаційну мережу, що поєднує всі міста комунікаційними лініями мінімальної вартості.
Існують різні методи побудови остовних дерев мінімальної вартості. Багато хто з них ґрунтуються на наступній властивості остовних дерев мінімальної вартості. Нехай G = (V, Е) -- зв'язний граф із заданою функцією вартості, що задана на множині ребер. Позначимо через U підмножину вершин V. Якщо (і, v) -- таке ребро найменшої вартості, що й належить U і v належить V \ U, тоді для графа G існує остовное дерево мінімальної вартості, що містить ребро (і, v).
Існують два популярних алгоритми побудови остовного дерева мінімальної вартості для позначеного графа G = (V, Е), основані на описаній властивості: Прима й Крускала. Обидва алгоритми відповідають «жадібній» стратегії: на кожному кроці вибирається локально найкращий варіант.
Алгоритм Прима поступово будує шуканий мінімальний остов, додаючи до нього по одному ребру на кожному кроці (Це означає, що алгоритм Прима є жадібним. Більш того, справедливість алгоритму Прима легко встановлюється в рамках теорії матроідов.). На початку роботи алгоритму результуюче дерево складається з однієї вершини (її можна вибирати довільно). Алгоритм складається з N-1 ітерації, на кожній з яких до дерева додається рівно одне ребро, не порушує властивості дерева (тобто один кінець додається ребра належить дереву, а інший - не належить). Ключовий момент - з усіх таких ребер кожен раз вибирається ребро з мінімальною вагою. Така реалізація працює за O (MN).
Покращена реалізація буде виконуватися помітно швидше - за O (M log N + N2).
Для цього ми відсортуємо всі ребра в списках суміжності кожної вершини по збільшенню ваги (буде потрібно O (M log M) = O (M log N)). Крім того, для кожної вершини заведемо покажчик, який вказує на перше доступне ребро в її списку суміжності. Спочатку всі покажчики вказують на початку списків, тобто рівні 0. На i-ої ітерації алгоритму Прима ми перебираємо всі вершини, і вибираємо найменше за вагою ребро серед доступних. Оскільки всі ребра вже відсортовані за вагою, а покажчики вказують на перші доступні ребра, то вибір найменшого ребра здійсниться за O (N). Тепер нам слід оновити покажчики, оскільки деякі з них вказують на що стали недоступними ребра (обидва кінці яких опинилися всередині дерева), тобто зрушити деякі з них праворуч. Проте, оскільки у всіх списках суміжності в сумі 2 * M елементів, а покажчики зсуваються тільки вправо, то виходить, що на підтримку всіх покажчиків потрібно O (M) дій. Разом - час виконання алгоритму O (MlogM + N2 + M), тобто O (M log N + N2)
Алгоритм Крускала спочатку поміщає кожну вершину в своє дерево, а потім поступово об'єднує ці дерева, об'єднуючи на кожній ітерації два деяких дерева деяким руба. Перед початком виконання алгоритму, усі ребра сортуються за вагою (в порядку неубиванія). Потім починається процес об'єднання: перебираються всі ребра від першого до останнього (у порядку сортування), і якщо у поточного ребра його кінці належать різним піддерев, то ці піддерев об'єднуються, а ребро додається до відповіді. Після закінчення перебору всіх ребер всі вершини опиняться належать одному піддереві, і відповідь знайдений.
Сортування ребер потребують O (M log N) операцій. Приналежність вершини того чи іншого піддереві зберігається просто за допомогою масиву, об'єднання двох дерев здійснюється за O (N) простим проходом по масиву. Враховуючи, що всього операцій об'єднання буде N-1, ми й отримуємо асимптотики O (M log N + N2).
Покращена реалізація використовує структуру даних "Система непересічних множин" позволет домогтися асимптотики O (M log N). Так само, як і в простій версії алгоритму Крускала, відсортуємо усі ребра по неубиванію ваги. Потім помістимо кожну вершину в своє дерево (тобто своє безліч) на це піде в сумі O (N). Перебираємо усі ребра (у порядку сортування) і для кожного ребра за O (1) визначаємо, чи належать його кінці різних деревам (за допомогою двох викликів FindSet за O (1)). Нарешті, об'єднання двох дерев буде здійснюватися викликом Union - також за O (1). Разом ми отримуємо асимптотики O (M log N + N + M) = O (M log N).
// сортируем список ребер по неубыванию
for (i = 0;i< n;i++) // цикл по вершинам
r[i] = i; // у вершина своя компонента связности
s[i] = 0; // размер компоненты связности
for (i = 0;i< n-1;i++) // цикл по ребрам mst
while (r[p]!=p) // ищем корень для p //
while (r[q]!=q) // ищем корень для q }
printf("%d %d\n",a[k].x, a[k].y); // вывод ребра
if (s[p] < s[q]) // взвешенное объединение
В результаті виконання програм ми переконалися, що вони дають однакове мінімальне остове дерево, яке має вигляд:
Висновок. Якщо кількість вершин достатньо мала, то доцільніше використовувати алгоритм Прима, в іншому випадку доцільно користуватися алгоритмом Крускала.
const int maxn = 100, inf = MAXINT/2, Max = 10000;
int d[maxn], n, mst_weight, pr_count, sr_count;
a[y-1][x-1] = z; // если неориентированный граф
printf("Min ostove derevo (by Prim)\n");
printf("Vaga dereva = %d\n", mst_weight);
printf("Time = %f\n", (end-start)/CLK_TCK);
printf("Comparison = %d\n", pr_count);
printf("Assignment = %d \n", sr_count);
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const int maxn = 10, maxm = 1000, inf = MAXINT/2, Max = 10000;
int s[maxn]; // размер компонент связности
int r[maxn]; // связи вершин в компонентах связности
int mst_weight; // вес минимального остовного дерева
int pr_count,sr_count; // кол-во присваиваний и сравнений
// построение mst (алгоритм Крускала)
printf("Min ostove derevo (by Kruskalo)\n");
printf("Vaga dereva = %d\n", mst_weight);
printf("Time = %f\n", (end-start)/CLK_TCK);
printf("Comparison = %d\n", pr_count);
printf("Assignment = %d \n", sr_count);
//---------------------------------------------------------------------------
1. Кормен Т., Лейзенсон Ч., Ривест Р. Алгоритмы: построрение и анализ. - М. : МЦНМО, 2001. - 960 с.
Остовное дерево связного неориентированного графа. Алгоритм создания остовного дерева, его нахождение. Сущность и главные особенности алгоритма Крускала. Порядок построения алгоритма Прима, вершина наименьшего веса. Промежуточная структура данных. презентация [140,8 K], добавлен 16.09.2013
Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации. курсовая работа [225,0 K], добавлен 30.04.2011
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе. курсовая работа [625,4 K], добавлен 30.09.2014
Нове уточнення поняття алгоритму вітчизняним математиком Марковим: 7 уточнених ним параметрів. Побудова алгоритмів з алгоритмів. Універсальний набір дій по управлінню обчислювальним процесом. Нормальні алгоритми Маркова. Правило розміщення результату. реферат [48,7 K], добавлен 30.03.2009
Точне знаходження первісної й інтеграла для довільних функцій. Чисельне визначення однократного інтеграла. Покрокові пояснення алгоритму методу Чебишева, реалізованого засобами програмування СКМ Mathcad. Знаходження інтегралу за допомогою панелі Calculus. курсовая работа [390,8 K], добавлен 19.05.2016
Побудування графа та матриці інцидентності. Перетворення графа у зважений за допомогою алгоритму Дейкстри, знаходження довжини найкоротшого шляху між двома вершинами та побудування дійсного шляху. Обхід дерева у прямому та зворотному порядках. курсовая работа [144,1 K], добавлен 03.07.2014
Дослідження основних статистичних понять та їх застосування в оціночній діяльності. Характеристика методів групування статистичних даних по якісним та кількісним прикметам. Вивчення алгоритму побудови інтервального ряду, розрахунок розмаху варіації. лекция [259,0 K], добавлен 07.02.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала курсовая работа. Математика.
Контрольная Работа По Немецкому Бим
Сочинение Про Мою Будущую Профессию На Английском
Курсовая работа: Судебная экспертиза
Контрольная работа: Общая и специальная физическая подготовка волейболистов
Виды Энергии Реферат
Әдеби Талдау Эссе
Итоговое Сочинение 2022 Тема Память
Мини Сочинение Про Стивена Кинга
Эсс 80.100 Москва
Как Писать Сочинение Про Историческую Личность
Курсовая работа по теме Характеристика государства Индонезия и возможности развития туризма
Контрольная работа по теме Использование экономико-математического моделирования в животноводстве
Первая Помощь При Отравлениях Реферат
Курсовая работа по теме Рынок интеллектуальной собственности
Понятие И Сущность Бизнеса Реферат
Реферат: Мировой финансовый кризис и экономика России. Скачать бесплатно и без регистрации
Курсовая Работа На Тему Поведение Потребителей
Реферат: Карпатский экономический регион Украины
Шпаргалка: Ответы по микроэкономике
Ремонт Радиоприемника Океан Рп 245 Курсовая
Понятие мезологистики - Маркетинг, реклама и торговля курсовая работа
Место и роль органов внутренних дел в современном государстве - Государство и право дипломная работа
Эколого-правовой режим лесопользования - Государство и право контрольная работа