Конспект: эвристический поиск

Понятия

A* - Дейкстра, выбирающая вершину по f(v) = g(v) + h(v):

g(v) - реально пройденное расстояние от старта
h(v) - ОЦЕНКА остатка до цели (дешёвая формула, не поиск)
f(v) - оценка полной длины пути через v

Допустимость - h(v) <= d(v, цель): эвристика не переоценивает остаток.

Согласованность (монотонность) - h(u) <= w(u, v) + h(v) и h(цель) = 0.

Иерархия сокращений - вершины сжимают от неважных к важным; если у пары соседей нет свидетеля (обхода не длиннее пути через v), добавляют сокращение. Запрос - две Дейкстры только вверх по рангу, ответ - минимум суммы в общей вершине.

Что унести

A* = Дейкстра на перевешенном графе:  w'(u, v) = w(u, v) + h(v) − h(u)
длина любого пути меняется на h(v) − h(старт)  ⇒ порядок путей сохраняется
согласованность ⇔ w' ≥ 0  ⇒ извлечённая вершина окончательна

Согласованность влечёт допустимость (складываем неравенства вдоль пути - телескопическая сумма); обратное неверно, и с допустимой-но-несогласованной эвристикой ПЕРЕОТКРЫТИЯ обязательны.

Надёжный способ получить эвристику - точно решить УПРОЩЁННУЮ задачу: разрешить ходить сквозь стены (манхэттенское или евклидово расстояние), игнорировать пробки, позволить фишкам прыгать. На дорожных графах берут ориентиры и неравенство треугольника (семейство ALT).

Тихие ошибки: остановиться, когда цель ПОПАЛА в очередь, а не когда извлечена; забыть h(цель) = 0; считать эвристику дорого; использовать множество закрытых вершин с несогласованной эвристикой; брать «расстояние по прямой» там, где вес ребра - не расстояние, а цена.

Асимптотика в худшем случае та же, что у Дейкстры: O((V + E)·log V). Выигрыш практический - в числе раскрытых вершин (на открытой сетке это разница между миллионом и парой тысяч).

Куда это ведёт

Следующая глава - минимальные остовные деревья: свойство разреза, Прим, Крускал и Борувка.