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

Содержание

• 
  Слайд 1

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

  Підготував: студент групи ФЕІ-41 Коблан Ігор

• 
  Слайд 2

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

• 
  Слайд 3

  Алгоритм Террі

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

• 
  Слайд 4

  Обхід графів

• 
  Слайд 5
  

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

• 
  Слайд 6

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

• 
  Слайд 7
  

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

• 
  Слайд 8

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

• 
  Слайд 9

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

• 
  Слайд 10
  

  Алгоритм на графах, який знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини. АлгоритмДейкстри  

• 
  Слайд 11

  Алгоритм Белмана — Форда

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

• 
  Слайд 12

  Алгоритм Флойда-Уоршола

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

• 
  Слайд 13
  
• 
  Слайд 14

  Алгоритм Джонсона

  Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює, якщо у графі містяться ребра з додатними чи від’ємними вагами, але відсутні негативні цикли.

• 
  Слайд 15

  Висновки

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

• 
  Слайд 16

  Дяую за увагу