Сравнительный анализ алгоритмов поиска пути

Курсовая работа

По теме:

«Приложение «Имитация движения транспортного средства по пересеченной местности »

 

 

Выполнил:

Студент гр. 124-1 Кузнецова Анастасия Вячеславовна

Проверил: научный руководитель, заместитель директора по учебной работе ИМКН, к.т.н, доцент кафедры программного обеспечения ИМКН «Тюменский государственный университет» Воробьева Марина Сергеевна

 

Тюмень 2012

Введение

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

Задачей курсовой работы выявление актуальности данной темы и поиск сферы применения данной программы, изучение и анализ алгоритмов поиска пути по карте без графов дорог, применение этих алгоритмов для создания программного продукта, описание работы данной программы.

 

Алгоритмы

Алгоритм Дейкстры

 

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм поиска пути на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных или до заданной конечной. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

 

Принцип работы

 

Каждой вершине сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

 

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

 

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

 

Эффективность алгоритма

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

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

В противном случае, алгоритм Дейкстры по всем параметрам уступает своей модификации – алгоритму A*(A-star, см. подраздел «Алгоритм A*»). Причиной различий служит то, что алгоритм Дейкстры будет проверять узлы графа равномерно в порядке удаления от начального, а A* отдаёт предпочтения тем узлам, которые по результатам эвристических расчётов ближе к конечному узлу, а значит, с большей вероятностью, будут принадлежать конечному пути. Таким образом, за счёт использования не затратной эвристической функции, A* будет проверять не больше, а на практике – значительно меньше узлов графа, чем алгоритм Дейкстры, а значит, будет работать быстрее.

 

Волновой алгоритм

 

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

 

Начальное значение волны - ноль.

 

На первой итерации, начальное значение волны – 0. Граничащие с волной точки(в начале – одна начальная точка), получают значение волны + некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 1.

 

Далее на каждой итерации значение волны увеличивается на 1 и схожим образом обрабатываются все узлы графа, в которые можно перейти из уже обработанных, и которые ещё не затронуты волной. Цикл останавливается, когда будет обработан узел конца пути.

 

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

 

§1.3 Алгоритм A*

 

История создания

В 1964 году Нильс Нильсон изобрел эвристический подход к увеличению скорости алгоритма Дейкстры. Этот алгоритм был назван А1. В 1967 году Бертрам Рафаэль сделал значительные улучшения по этому алгоритму, но ему не удалось достичь оптимальности. Он назвал этот алгоритм A2. Тогда в 1968 году Петр Э. Харт представил аргументы, которые доказывали, что A2 был оптимальным при использовании последовательной эвристики лишь с незначительными изменениями. В его доказательство алгоритма также включен раздел, который показывал, что новый алгоритм A2 был, возможно, лучшим алгоритмом, учитывая условия.

 

Принцип работы

 

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

 

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Сначала рассматриваются те маршруты, которые «кажутся» ведущими к цели. В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение эвристической функции, после чего этот узел раскрывается.

 

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

 

В случае с двумерным массивом, A* действует подобно направленному волновому алгоритму, поэтому при достижении им конечной точки, формирование кратчайшего пути уже становится возможным и совершается незамедлительно.

 

Эффективность.

Алгоритм A* на данный момент является оптимальным способом поиска пути между двумя точками в тех случаях, когда существует сравнительно простой эвристический метод оценки расстояния между элементами области поиска. Если такого метода не существует, A* идентичен либо алгоритму Дейкстры в вариации для двух точек, либо волновому алгоритму в зависимости от вида области поиска.

 

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

Сравнительный анализ алгоритмов поиска пути

 

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

 

· Алгоритм Дейкстры приоритетен в случаях поиска пути до всех точек области поиска, а также в случае отсутствия сколь либо эффективной эвристической функции оценки расстояния между элементами области поиска.

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

· Алгоритм A* эффективен при одиночном поиске пути между двумя точками, если возможно эффективно эвристически получать примерную дистанцию между элементами области поиска.

· Навигационная сетка с использованием алгоритма A* эффективна при создании AI, в чьи задачи входит не только поиск пути. Также этот метод эффективен при необходимости построить реалистичную сглаженную траекторию движения между двумя точками. Данный метод предполагает наличие детальной информации об области поиска или возможности получения такой информации.

· Эвристические алгоритмы поиска пути применимы и оптимальны, если необходим максимально простой алгоритм, при этом область поиска достаточно проста, а применения алгоритма допускают неточность полученного пути.