С каждым днём человек всё больше и больше ощущает нехватку свободного времени и избыток дел, мы предлагаем свой вариант решения данной проблемы.
Что может помочь сэкономить время на выполнение задачи? Наш ответ - поиск кратчайшего пути. Ведь чем путь короче, тем быстрее он преодолевается. Для оптимизации пути была создана модель, которая содержит в себе главную загвоздку – препятствия, не будь их, кратчайший путь был бы просто дугой по поверхности Земли, ну или прямой на плоскости.
Моделируя мир, мы упростили задачу по созданию и прохождению препятствий: в нашей модели препятствия могут быть только кругами, то есть задаются координатами центра и радиусом. Далее мы решили зафиксировать минимальное и максимальное значение шага и угла поворота. Параметры могут принимать значения из достаточно большого интервала, описывая разные ситуации, однако наилучшей иллюстрацией к данному проекту будет движение человека, бегущего по полю с лужами.
Постановка задачи: сформулировать алгоритм, и реализовать его в виде программы. Программа должна находить кратчайший путь от начальной точки до конечной, обходя препятствия, представляющие собой окружности, с заданными первым, максимальным, минимальным шагами и максимальным углом отклонения от направления предыдущего шага и максимальной длиной пути.
Поставленную задачу будем решать на графе. Разбиваем пространство с определённым шагом на вершины.
При построении возможных путей на каждом шаге нам необходимо строить множество шагов возможных в данном случае (с учётом заданных длины шага и угла поворота). Введём понятие маски хода – заранее просчитанное множество пар: предыдущий шаг – множество возможных следующих из него. С помощью масок ходов мы создаём для себя трафарет, использование которого значительно ускоряет построение пути.
Шаг – переход из одной точки в другую, имеет начало, конец, длину.
Путь – совокупность последовательных шагов, сделанных с учётом ограничений Продлённый путь – путь, для последнего шага которого посчитана маска хода. Наша программа строит все возможные варианты путей, затем выбирая из них кратчайший.
Порядок обхода путей определяется эвристической функцией «длина пройдённого пути + расстояние от конца пути до конечной точки». Мы выбираем непродлённый путь, для которого значение этой функции минимально. Данное условие выбора пути позволяет утверждать, что первый найденный путь, пришедший в конечную точку не длиннее других возможных.
Алгоритм:
Расчёт маски хода, построение первого шага, с пройденным расстоянием – ноль.
Поиск непродлённого пути, для которого значение эвристической функции минимально.
Если такого пути нет – искомого пути не существует. Выход из алгоритма.
Построение маски хода (продление пути) для найденного шага (продление).
Проверка на препятствие – отсев точек, которые попадают внутрь препятствий.
Проверка на длину пути. Отбрасываем пути, длина которых больше предельной.
Проверка на достижение конечной точки.
Если на данный момент найден путь, достигающий конечной точки – этот путь искомый. Выход из алгоритма.
Переход к пункту 1.
Данный алгоритм был реализован на СУБД MySQL, интерфейс программы на — C#. Выбор СУБД в качестве языка обоснован тем, что алгоритм работает с большим объёмом данных (вершины, шаги, пути, препятствия), но при этом большие функциональные возможности от языка не требуются (сложение, умножение, поиск минимума и максимума).
Приводим рабочий пример программы. Рисунок 1 иллюстрирует входные данные. Рисунок 2 иллюстрирует решение, найденное программой
Рис.1
Начальный шаг (из оранжевой точки в красную),
2- препятствия, 3 -конечная точка.
Рис.2
1 -найденный путь, 2 – точки, которые участвовали в проложении путей (появившиеся при наложении маски ходов).
Рис.3
Рис.4 – результат работы для начальных данных, представленных на Рис.3
Данный алгоритм может быть усовершенствован по нескольким параметрам: изменение формы возможных препятствий (многоугольники), запрет пересечения препятствий, отдельная логика для вырожденных случаев (угол поворота 180°, минимальный шаг 0).
Работа может быть использована в многочисленных программах GPS навигации, интернет-картах, и для компаний, производящих грузовые перевозки.
Данная статья написана на основе курсовой работы по теме: «Поиск кратчайшего пути» выполненной под руководством преподавателя Костоусова В.Б. на кафедре прикладной математики Уральского энергетического института УрФУ имени первого Президента России Б.Н. Ельцина.