«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» (ФГБОУ ВПО ВГУ)
Воронеж - 2015г
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Нахождение оптимального маршрута с пересадками на железной дороге презентация
Содержание
- 1. Нахождение оптимального маршрута с пересадками на железной дороге
- 2. Железнодоро́жный тра́нспорт — вид наземного транспорта, перевозка грузов и пассажиров на котором осуществляется колёсными
- 3. Не смотря на огромную протяженность железных
- 4. По статистике, если человек едет не из
- 5. Были разработаны: алгоритм для поиска оптимального
- 6. ГРАФ Для обсуждения данного алгоритма необходимо понимание
- 7. АЛГОРИТМ ПОСТРОЕНИЯ ГРАФА Обычно вершинами графа являются
- 8. ПОСТРОЕНИЕ ГРАФА
- 9. АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ В качестве алгоритма
- 10. АЛГОРИТМ ДЕЙКСТРЫ Присвоение нулевого потенциала начальной вершине
- 12. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ Для написания программы была выбрана
- 13. ЗАДАНИЕ МАРШРУТА
- 14. ПОЛУЧЕННЫЙ РЕЗУЛЬТАТ
- 15. Спасибо за внимание!
Железнодоро́жный тра́нспорт — вид наземного транспорта, перевозка грузов и пассажиров на котором осуществляется колёсными транспортными средствами по рельсовым путям. Железнодоро́жный тра́нспорт Протяженность железнодорожной сети в России около 100 000 км. Максимальная скорость железнодорожного сообщения в России (состав Сапсан): Москва
Слайд 1НАХОЖДЕНИЕ ОПТИМАЛЬНОГО МАРШРУТА С ПЕРЕСАДКАМИ НА ЖЕЛЕЗНОЙ ДОРОГЕ
Разработал: Золотухин Дмитрий Игоревич
Научный
руководитель: Горбенко Олег Данилович
Слайд 2Железнодоро́жный тра́нспорт — вид наземного транспорта, перевозка грузов и пассажиров на котором осуществляется колёсными транспортными средствами по рельсовым путям.
Железнодоро́жный тра́нспорт
Протяженность
железнодорожной сети в России около 100 000 км.
Максимальная скорость железнодорожного сообщения в России (состав Сапсан): Москва – Санкт-Петербург – 250 км/ч.
Слайд 3Не смотря на
огромную протяженность железных дорог
относительно большую скорость перемещения
для наземного транспорта
невероятное количество поездов, ежедневно движущихся по нашей стране
данный вид транспорта до сих пор являет самым безопасным.
невероятное количество поездов, ежедневно движущихся по нашей стране
данный вид транспорта до сих пор являет самым безопасным.
Т.е. при выборе транспорта для перемещения на большие расстояния велика вероятность, что человек выберет именно поезд.
ВЫБОР ТРАНСПОРТА
Слайд 4 По статистике, если человек едет не из Москвы, то он с
вероятностью чуть меньше 50% будет ехать с пересадкой.
Однако нахождение верного маршрута с пересадками до сих пор является не самой простой и очевидной задачей. РЖД запускает на своем сайте сервис для поиска поездов с пересадками, однако пока что
он работает в тестовом режиме.
Однако нахождение верного маршрута с пересадками до сих пор является не самой простой и очевидной задачей. РЖД запускает на своем сайте сервис для поиска поездов с пересадками, однако пока что
он работает в тестовом режиме.
ПРОБЛЕМЫ ПАССАЖИРОВ
Слайд 5Были разработаны:
алгоритм для поиска оптимального маршрута перемещения по железной дороге,
с пересадками;
программа, использующая данный алгоритм.
программа, использующая данный алгоритм.
РАЗРАБОТАННЫЙ ПРОДУКТ
Слайд 6ГРАФ
Для обсуждения данного алгоритма необходимо понимание определения графа.
Граф – совокупность непустого
множества вершин и наборов пар вершин (связей между вершинами)
Существует множество различных алгоритмов для нахождения кратчайшего пути в графе, так называемой, задаче о кратчайшем пути. Однако данные алгоритмы не рассматривают тот факт, что поезда движутся по маршрутам.
Существует множество различных алгоритмов для нахождения кратчайшего пути в графе, так называемой, задаче о кратчайшем пути. Однако данные алгоритмы не рассматривают тот факт, что поезда движутся по маршрутам.
Слайд 7АЛГОРИТМ ПОСТРОЕНИЯ ГРАФА
Обычно вершинами графа являются станции, а дороги - его
ребрами, однако придуманный алгоритм использует другую методику построения графа.
Таким образом, для использования одного из уже существующих алгоритмов маршруты поездов были заменены на вершины графа. Вершины полученного графа соединяются в том случае, если маршруты поездов пересекаются.
Таким образом, для использования одного из уже существующих алгоритмов маршруты поездов были заменены на вершины графа. Вершины полученного графа соединяются в том случае, если маршруты поездов пересекаются.
Слайд 9АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ
В качестве алгоритма поиска кратчайшего пути в графе
выбрана методика Дейкстры.
Главное условие этой методики – положительные длины дуг. В нашем случае это условие выполняется, так как время и стоимость – величины положительные.
Слайд 10АЛГОРИТМ ДЕЙКСТРЫ
Присвоение нулевого потенциала начальной вершине и потенциала-бесконечность конечной вершине; начальная
вершина окрашивается;
Потенциал каждой вершины ищется по формуле:
d(x) = min {d(x), d(y)+a(y,x)},
где y – последняя окрашенная вершина, х – текущие вершины,
a(y,x) – длина дуги (y,x); Выбранная вершина х окрашивается;
Полученный окрашенный путь - кратчайший
Потенциал каждой вершины ищется по формуле:
d(x) = min {d(x), d(y)+a(y,x)},
где y – последняя окрашенная вершина, х – текущие вершины,
a(y,x) – длина дуги (y,x); Выбранная вершина х окрашивается;
Полученный окрашенный путь - кратчайший
Слайд 12ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
Для написания программы была выбрана платформа .NET и язык C#.
.NET представляет собой удобный постоянно развивающийся способ разработки приложений.
Платформа .NET является полностью независимой от используемых языков программирования, и позволяет использовать несколько .NET-совместимых языков программирования даже в рамках одного проекта.
