Применение
Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами
Как это работает?
На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).
Псевдокод
q.push(start)
while (!q.empty()) {
v = q.top()
q.pop()
for u, cost : graph[v] {
func = dist[v] + cost + heuristic(u)
if (func < f[u]) {
if (u in q) {
// изменим значение функции у вершины u в куче
} else {
// добавим u в кучу
}
}
}
}
Как выбирать эвристику?
Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).
Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.
Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!
Примеры
А теперь посмотрим примеры эвристик:
1) Нахождение гамильтоново пути, в этой задаче можно для некоторых случаев решать довольно быстро с помощью алгоритма A* (просто будем поддерживать посещённые вершины и последнюю в паре в куче) в качестве эвристики возьмём вес минимального остова на оставшихся вершинах, A* позволит в таком случае оптимизировать количество рассмотренных вариантов путей и соответственно сложность алгоритма.
2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).
3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}
4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)
Одну из задач на этот алгоритм вы можете сдать здесь. А так реализация этого алгоритма простая, всё заключается в правильном подборе эвристики.
@algoses