Редактирование: Алгоритм A*

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
==Описание==
 
==Описание==
[[Файл:Astar_progress_animation.gif|right|frame|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
 
 
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где  
 
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где  
 
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,  
 
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,  
Строка 8: Строка 7:
 
Фактически, функция <tex>f(v)</tex> {{---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v)</tex> и оставшегося расстояния <tex>h(v)</tex>. Исходя из этого, чем меньше значение <tex>f(v)</tex>, тем раньше мы откроем вершину <tex>v</tex>, так как через неё мы предположительно достигнем расстояние до цели быстрее всего.
 
Фактически, функция <tex>f(v)</tex> {{---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v)</tex> и оставшегося расстояния <tex>h(v)</tex>. Исходя из этого, чем меньше значение <tex>f(v)</tex>, тем раньше мы откроем вершину <tex>v</tex>, так как через неё мы предположительно достигнем расстояние до цели быстрее всего.
 
Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.  
 
Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.  
<br clear="all">
+
 
 
==Свойства==
 
==Свойства==
 
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
 
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
Строка 43: Строка 42:
  
 
==Примеры эвристик==
 
==Примеры эвристик==
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.
+
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
  
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<ref>[https://en.wikipedia.org/wiki/Manhattan_distance Wikipedia {{---}} Manhattan distance]</ref><br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  
+
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  
  
* Расстояние Чебышева<ref>[https://ru.wikipedia.org/wiki/Расстояние_Чебышева Википедия {{---}} Расстояние Чебышева]</ref> применяется, когда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}</tex>.
+
* [http://ru.wikipedia.org/wiki/Расстояние_Чебышева Расстояние Чебышева] применяется когда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}</tex>.
  
 
* Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:<br> <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>.
 
* Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:<br> <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>.
Строка 55: Строка 54:
 
==Реализация==
 
==Реализация==
 
В приведённой реализации:
 
В приведённой реализации:
* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть,
+
* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть
* <tex>U</tex> {{---}} множество рассмотренных вершин,
+
* <tex>U</tex> {{---}} множество рассмотренных вершин
* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>,
+
* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>
* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>,
+
* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>
 
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
 
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
 
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество <tex>Q</tex>.<br>
 
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество <tex>Q</tex>.<br>
Строка 75: Строка 74:
 
         U.push(current)
 
         U.push(current)
 
         '''for''' v : смежные с current вершины
 
         '''for''' v : смежные с current вершины
             tentativeScore = g[current] + d(current, v)           <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font>  
+
             tentative_score = g[current] + d(current, v)         <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font>  
             '''if''' <tex>v \in U</tex> '''and''' tentativeScore >= g[v]
+
             '''if''' <tex>v \in U</tex> '''and''' tentative_score >= g[v]
 
                 '''continue'''
 
                 '''continue'''
             '''if''' <tex>v \notin U</tex> '''or''' tentativeScore < g[v]
+
             '''if''' <tex>v \notin U</tex> '''or''' tentative_score < g[v]
 
                 parent[v] = current
 
                 parent[v] = current
                 g[v] = tentativeScore
+
                 g[v] = tentative_score
 
                 f[v] = g[v] + h(v)
 
                 f[v] = g[v] + h(v)
 
                 '''if''' <tex>v \notin Q</tex>
 
                 '''if''' <tex>v \notin Q</tex>
Строка 88: Строка 87:
 
==См. также==
 
==См. также==
 
* [[Эвристики для поиска кратчайших путей]]
 
* [[Эвристики для поиска кратчайших путей]]
* [[Алгоритм Флойда]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Форда-Беллмана]]
 
  
 
==Примечания==
 
==Примечания==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)