Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему “Алгоритми пошуку оптимального рішення задачі та найкоротшого шляху”

Пошук маршруту у графі
“Алгоритми пошуку оптимального рішення задачі та найкоротшого шляху” Підготував: студент групи ФЕІ-41Коблан Ігор Пошук маршруту у графі Алгоритм ТерріЗнаходить шлях між двома вершинами графа Обхід графів Пошук у ширинуПошук у глибину Пошук відстані між вершинами графа Хвильовий алгоритм - алгоритм, що дозволяє знайти мінімальний шлях в графі з ребрами одиничної Приклад роботи Хвильового алгоритму Приклад роботи двонапрямленого Хвильового алгоритму Алгоритм на графах, який знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний Алгоритм Белмана — Форда	Алгоритм шукає найкоротший шлях від заданої вершини до всіх Алгоритм Флойда-Уоршола	Для k от 1 до |V| виконати Для i от 1 Алгоритм Джонсона	Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин зваженого ВисновкиПідіб’ємо підсумки. Якщо необхідно знайти відстань від однієї вершини до іншої або Дяую за увагу
Слайды презентации

Слайд 2 Пошук маршруту у графі

Пошук маршруту у графі

Слайд 3 Алгоритм Террі
Знаходить шлях між двома вершинами графа

Алгоритм ТерріЗнаходить шлях між двома вершинами графа

Слайд 4 Обхід графів

Обхід графів

Слайд 5 Пошук у ширину
Пошук у глибину

Пошук у ширинуПошук у глибину

Слайд 6 Пошук відстані між вершинами графа

Пошук відстані між вершинами графа

Слайд 7 Хвильовий алгоритм - алгоритм, що дозволяє знайти мінімальний шлях в

Хвильовий алгоритм - алгоритм, що дозволяє знайти мінімальний шлях в графі з ребрами

графі з ребрами одиничної довжини. Заснований на алгоритмі пошуку

в ширину. Застосовується для знаходження найкоротшого шляху в графі, в загальному випадку знаходить лише його довжину.

Хвильовий алгоритм


Слайд 8 Приклад роботи Хвильового алгоритму

Приклад роботи Хвильового алгоритму

Слайд 9 Приклад роботи двонапрямленого Хвильового алгоритму

Приклад роботи двонапрямленого Хвильового алгоритму

Слайд 10 Алгоритм на графах, який знаходить найкоротший шлях від однієї вершини графа до

Алгоритм на графах, який знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин.

всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для

графів без циклів від'ємної довжини.

Алгоритм Дейкстри  


Слайд 11 Алгоритм Белмана — Форда
Алгоритм шукає найкоротший шлях від

Алгоритм Белмана — Форда	Алгоритм шукає найкоротший шлях від заданої вершини до

заданої вершини до всіх інших. Ідея в тому, що

ми зберігаємо в масиві відстані до кожної вершини і на кожному кроці алгоритму оновлємо ці значення, якщо знайшли ребро яке покращує результат. Таким чином, після після кожного кроку матимемо масив найкоротших шляхів.

Слайд 12 Алгоритм Флойда-Уоршола
Для k от 1 до |V| виконати Для

Алгоритм Флойда-Уоршола	Для k от 1 до |V| виконати Для i от

i от 1 до |V| виконати Для j от

1 до |V| виконати Якщо вага i->k и k->j не нульові, и i не рівно j, то Якщо вага i->k + вес k->j меньше веса i->j, то заменить его их суммой

Матриця суміжності


Слайд 14 Алгоритм Джонсона
Алгоритм Джонсона дозволяє знайти найкоротші шляхи між

Алгоритм Джонсона	Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин

усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює,

якщо у графі містяться ребра з додатними чи від’ємними вагами, але відсутні негативні цикли.


Слайд 15 Висновки

Підіб’ємо підсумки. Якщо необхідно знайти відстань від однієї

ВисновкиПідіб’ємо підсумки. Якщо необхідно знайти відстань від однієї вершини до іншої

вершини до іншої або до всіх вершин графу і

ваги всіх ребер графу є додатними або дорівнюють нулю, то найбільш ефективним виявляється алгоритм Дейкстри із часом роботи О(m lgn). Якщо ж ваги ребер можуть бути від’ємними, то необхідно застосовувати алгоритм Белмана-Форда, час роботи якого О(nm).
Якщо необхідно знайти відстані між усіма парами вершин графу, граф є розрядженим і всі ребра мають невід’ємні ваги, то можна виконати n разів алгоритм Дейкстри. Якщо ж граф є розрядженим, але в ньому можуть бути ребра з від’ємними вагами, то необхідно використовувати алгоритм Джонсона. Якщо необхідно знайти відстані між усіма парами вершин, ваги ребер можуть бути від’ємними і граф не є розрядженим (m прямує до n2), то необхідно використовувати алгоритм Флойда-Уоршола.
Жоден з наведених алгоритмів не може бути застосований для графів, які містять негативні цикли. Проте алгоритм Белмана-Форда (як і алгоритм Джонсона), а також алгоритм Флойда-Уоршола можуть виявити такі цикли.

  • Имя файла: “algoritmi-poshuku-optimalnogo-rіshennya-zadachі-ta-naykorotshogo-shlyahu”.pptx
  • Количество просмотров: 142
  • Количество скачиваний: 0