Проекты

Поиск пути в топографических условиях

Работа призёра открытой городской научно-практической конференции «Инженеры будущего» в секции «Информационные технологии, моделирование, прототипирование, прикладная математика, социальный инжиниринг» среди индивидуальных работ учащихся 10−11 классов

Направление работы: Программирование
Авторы работы: ГБОУ Школа № 1363
Предметы: Информатика
Классы: 11 класс
Мероприятия: Открытая городская научно-практическая конференция «Инженеры будущего» 16−17 апреля 2018 года

Описание

В современном мире существует множество интересных и важных задач, в которых нахождение оптимального маршрута или пути является необходимым условием. Поиск кратчайшего пути – востребованная задача в современном мире, которая используется повсеместно: поиск кратчайшего маршрута на картах рельефа местности, поиск кратчайшего расстояния между контактами на печатной плате или наиболее удачного маршрута для передвижения роботов, машин. Существуют различные подходы к решению этих задач.

Задачи

Демонстрация и сравнение двух востребованных методов поиска кратчайшего пути, а также адаптация этих алгоритмов для решения задачи нахождения кратчайшего пути в топографических условиях (условия рельефа представляют собой перепады высот, разные типы местности и т. п., влияющие на сложность прохождения через конкретную точку).

Цель

Разработка и реализация наглядной программы, позволяющей строить наиболее оптимальный путь между выбранными пунктами, сравнивая множественные алгоритмы поиска пути, оценивая их скорость работы, а также методы ускорения работы этих алгоритмов.

Ход работы

В ходе исследовательской работы были рассмотрены и проанализированы разные алгоритмы поиска пути, связанные с задачей поиска как можно менее затратного по времени пути. Выявлены условия и особенности, при которых используются определённые типы алгоритмов поиска пути. В программе наглядно продемонстрированы результаты работы алгоритмов поиска пути.

Разработанная программа позволяет строить оптимальные маршруты в различных топографических условиях (сложность которых можно задавать) с демонстрацией временны́х затрат.

Возможности применения программы

1. Демонстрация работы выбранного алгоритма.

2. Сравнение выбранного алгоритма с другим алгоритмом поиска пути, нахождение наилучшего для представленных условий, определение проблемных мест.

3. Расчеты времени пути в реальных условиях