Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
План-конспект уроку
Тема уроку: Визначення найкоротшого шляху в графі, алгоритм Дейкстри.
Мета уроку: удосконалити знання та сформувати вміння та навички в учнів при вивченні алгоритму Дейкстри; ознайомити їх з алгоритмом; виховати наполегливість, спостережливість, розвинути логічне та абстрактне мислення.
Тип уроку: урок вивчення нового матеріалу.
Вид уроку: урок-бесіда.
Обладнання: комп’ютер, мультимедійна дошка, проектор.
Тривалість: 45 хвилин.
План уроку:
1. Організаційна частина. (2 хв)
2. Актуалізація опорних знань. (10 хв)
3. Пояснення нового матеріалу: (25 хв)
1) Визначення найкоротшого шляху в графі.
2. Закріплення нового матеріалу. (8 хв)
3. Домашнє завдання. (3 хв)
4 . Підсумок уроку. (2 хв)
Хід уроку
1. Організаційна частина.
Заходжу в клас, вітаюсь , перевіряю відсутніх і готовність учнів до заняття. Записую на дошці тему: “_________”.
2. Актуалізація опорних знань. (10 хв)
Задаю учням питання по попередній темі і запитую бажаючих відповідати. Якщо бажаючих немає, то піднімаю учнів за власним бажанням. Якщо учень відповідає невірно, прошу когось із учнів виправити відповідь товариша.
Найкоротший шлях у графі
|
В теорії графів, задача про найкоротший шлях полягає в знаходженні шляху між двома вершинами (або вузлами) такого графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами - відтинки дороги із вагами, рівними часу, необхідному для подолання цього відтинку. Така задача іноді згадується як Задача про найкоротший шлях між парою вершин, щоб відрізнити від наступних узагальнень: § Задача про найкоротші шляхи з одного входу, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графа. Ці узагальнення мають значно дієвіші алгоритми ніж спрощений підхід із запуском алгоритма пошуку найкоротшого шляху між всіми значимими парами вершин. Алгоритми Найважливіші алгоритми для розв'язання цієї задачі: § Алгоритм Дейкстри розв'язує задачі з однією парою, одним входом і одним виходом. § Алгоритм Беллмана-Форда розв'язує задачі з одним входом, якщо ваги ребер можуть бути від'ємні. § Алгоритм пошуку A* розв'язує задачу для однієї пари із використанням евристики в спробі пришвидшити пошук. § Алгоритм Флойда-Воршелла розв'язує задачу для всіх пар. § Алгоритм Джонсона розв'язує задачу для всіх пар, і може бути швидшим за алгоритм Флойда-Воршелла на розріджених графах. § Теорія збурень знаходить (в найгіршому випадку) локально найкоротший шлях. |
Алгоритм Дейкстри.
Обгрунтування алгоритму Дейкстри
Алгоритм Дейкстри — приклад алгоритму, де "жадібність" окуповується в тому сенсі, що якщо щось "добре" локально, то воно буде "'добре" і глобально. В даному випадку щось локально "добре" — це обчислена відстань від джерела до вершини w, яка поки не входить в множину S, але має найкоротший особливий шлях. (Нагадаємо, що особливим ми назвали шлях, який проходить тільки через вершини множини S.) Щоб зрозуміти, чому не може бути іншого найкоротшого, але не особливого. Тут показано гіпотетичний найкоротший шлях до вершини w, який спочатку проходить до вершини х через вершини множини S, потім після вершини х шлях, можливо, кілька разів входить до множини S і виходить з неї, поки не досягне вершини w.
Але якщо цей шлях коротше за найкоротший особливий шлях до вершини w, то і початковий сегмент шляху від джерела до вершини х (який теж є особливим шляхом) також коротше, ніж особливий шлях до w. Але у такому разі в рядку (5) тексту програми 6.3 при виборі вершини w ми повинні були вибрати не цю вершину, а вершину х, оскільки D[х] менше за D[w]. Таким чином, ми дійшли суперечності, отже, не може бути іншого найкоротшого шляху до вершини w, окрім особливого. (Відзначимо тут визначальну роль того факту, що всі вартості дуг невідємні, без цієї властивості поміченого орграфа алгоритм Дейкстри не працюватиме правильно.)
|
Алгоритм Дейкстри дозволяє знайти найкоротшу довжину шляху і визначити маршрт від стартової вершини А до кожної з інших вершин. Опис Алгоритму: Задано граф з N вершин, номер стартової вершини А і відома матриця ребер R (з урахуванням ∞ для пар вершин, між якими немає ребер). Знайти найкоротший маршрут з А до кожної з вершин і його довжину. Проілюструємо алгоритм на прикладі конкретного графа (див. рисунок) з N=5 вершин. Нехай потрібно знайти довжини всіх маршрутів від вершини А=2 до вершин 1…5. Виконаємо декілька операцій. Спочатку складаємо матрицю довжин ребер, користуючись рисунком.
Заведемо три масиви X, Y, Z довжиною N=5 і складемо початкову таблицю за такими правилами% a) У перший масив X записуємо нулі у всі комірки, крім X[2]=1. Одиницею помічатимемо переглянуті вершини. b) У другий масив впишемо довжини ребер від вершини 2 з матриці (або рисунка), тобто перенесемо другий рядок матриці. c) У третій массив запишемо всюди 2 (номер стартової вершини), крім комірки 2, куди впишемо 0. Домашнє завдання:___________________ |