Similar presentations:
Алгоритмы поиска кратчайших путей в графе
1.
Алгоритмы поиска кратчайших путей в графеАвтор: ученик 10А Рожок Алексей Дмитриевич
Руководитель: учитель информатики Петов Олег Владимирович
2.
АктуальностьСейчас эта тема как никогда актуальна. Каждый хоть раз пользовался онлайн
картами, в которых реализованы данные алгоритмы. Поэтому эта тема так важна
в наши дни, когда много людей по всему миру путешествуют и используют
карты.
В жизни встречается довольно большое количество задач, которые могут быть
переформулированы в указанном виде — например, задача определения
времени поездки в метро (и оптимального маршрута). Google использует
алгоритм Дейкстры для сортировки важности страниц в выдаче. Также
алгоритмы поиска кратчайшего пути используются для поиска наикратчайших
путей в навигаторах и онлайн картах.
3.
Цель и задачиЦель - Исследовать существующие алгоритмы поиска кратчайших путей.
Задачи индивидуального проекта для достижения цели:
1) Изучить самые известные алгоритмы для поиска кратчайших путей.
2) Описать работу алгоритмов.
3) Обосновать верность алгоритмов.
4.
5.
Алгоритм Форда-БеллманаАлгоритм носит имя двух американских
учёных: Ричарда Беллмана (Richard Bellman) и
Лестера Форда (Lester Ford). Форд фактически
изобрёл этот алгоритм в 1956 г. при изучении другой
математической задачи, подзадача которой свелась к
поиску кратчайшего пути в графе, и Форд дал
набросок решающего эту задачу алгоритма. Беллман
в 1958 г. опубликовал статью, посвящённую
конкретно задаче нахождения кратчайшего пути, и в
этой статье он чётко сформулировал алгоритм в том
виде, в котором он известен нам сейчас.
6.
Постановка задачи алгоритма Форда-БеллманаВ задаче рассматривается взвешенный граф
- то есть граф, каждому ребру которого сопоставлено
некоторое число, называемое его весом.
Давайте будем действовать итерационно.
Изначально известно расстояние только до
начальной вершины - оно равно 0. В каждый момент
времени мы можем проверить выполнение свойства
для какого-нибудь ребра и, если оно нарушено,
улучшить существующую оценку расстояния до
конечной вершины ребра. Это процедура называется
релаксацией.