VI Международная студенческая научная конференция Студенческий научный форум - 2014

В работе производится поиск кратчайшего пути с обходом препятствий.

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

Что может помочь сэкономить время на выполнение задачи? Наш ответ - поиск кратчайшего пути. Ведь чем путь короче, тем быстрее он преодолевается. Для оптимизации пути была создана модель, которая содержит в себе главную загвоздку – препятствия, не будь их, кратчайший путь был бы просто дугой по поверхности Земли, ну или прямой на плоскости.

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

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

Поставленную задачу будем решать на графе. Разбиваем пространство с определённым шагом на вершины.

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

Шаг – переход из одной точки в другую, имеет начало, конец, длину.

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

Порядок обхода путей определяется эвристической функцией «длина пройдённого пути + расстояние от конца пути до конечной точки». Мы выбираем непродлённый путь, для которого значение этой функции минимально. Данное условие выбора пути позволяет утверждать, что первый найденный путь, пришедший в конечную точку не длиннее других возможных.

Алгоритм:

1. Расчёт маски хода, построение первого шага, с пройденным расстоянием – ноль.

2. Поиск непродлённого пути, для которого значение эвристической функции минимально.

   1. Если такого пути нет – искомого пути не существует. Выход из алгоритма.

   2. Построение маски хода (продление пути) для найденного шага (продление).

3. Проверка на препятствие – отсев точек, которые попадают внутрь препятствий.

4. Проверка на длину пути. Отбрасываем пути, длина которых больше предельной.

5. Проверка на достижение конечной точки.

   1. Если на данный момент найден путь, достигающий конечной точки – этот путь искомый. Выход из алгоритма.

   2. Переход к пункту 1.

Данный алгоритм был реализован на СУБД MySQL, интерфейс программы на — C#. Выбор СУБД в качестве языка обоснован тем, что алгоритм работает с большим объёмом данных (вершины, шаги, пути, препятствия), но при этом большие функциональные возможности от языка не требуются (сложение, умножение, поиск минимума и максимума).

Приводим рабочий пример программы. Рисунок 1 иллюстрирует входные данные. Рисунок 2 иллюстрирует решение, найденное программой

Рис.1

1. Начальный шаг (из оранжевой точки в красную),

2- препятствия, 3 -конечная точка.

Рис.2

1 -найденный путь, 2 – точки, которые участвовали в проложении путей (появившиеся при наложении маски ходов).

Рис.3

Рис.4 – результат работы для начальных данных, представленных на Рис.3

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

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

Данная статья написана на основе курсовой работы по теме: «Поиск кратчайшего пути» выполненной под руководством преподавателя Костоусова В.Б. на кафедре прикладной математики Уральского энергетического института УрФУ имени первого Президента России Б.Н. Ельцина.

 

Код для цитирования: Скопировать