ЭУМКД_ДиВМ3

АлгоритмА*

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

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

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. При выборе вершины А* учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей). В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).

Псевдокод алгоритма:

function A*(start,goal)

closedset := the empty set // The set of nodes already evaluated.

openset := set containing the initial node // The set of tentative nodes to be evaluated.

came_from := the empty map // The map of navigated nodes.

g_score[start] := 0 // Cost from start along best known path.

h_score[start] := heuristic_cost_estimate(start, goal)

f_score[start] := h_score[start] // Estimated total cost from start to goal through y.

while openset is not empty

x := the node in openset having the lowest f_score[] value

if x = goal

return reconstruct_path(came_from, came_from[goal])

remove x from openset

add x to closedset

foreach y in neighbor_nodes(x)

if y in closedset

continue

tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset

add y to openset

tentative_is_better := true

else if tentative_g_score < g_score[y]

tentative_is_better := true

else

tentative_is_better := false

if tentative_is_better = true

came_from[y] := x

g_score[y] := tentative_g_score

h_score[y] := heuristic_cost_estimate(y, goal)

f_score[y] := g_score[y] + h_score[y]

return failure

end function A*

function reconstruct_path(came_from, current_node)

if came_from[current_node] is set

p = reconstruct_path(came_from, came_from[current_node])

return (p + current_node)

else

return current_node

endfucntion reconstruct_path

Дополнительную информацию по алгоритму A* можно найти в свободной энциклопедии Wikipedia: http://en.wikipedia.org/wiki/A*_search_algorithm

__________________________________________________________

Дополнительнаяинформация:

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

Шаг 1

Шаг 2

Шаг 3

Шаг 4.

Содержание