Эвристические алгоритмы

Эвристический алгоритм - алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который точно известно, что он дает достаточно хорошее решение в большинстве случаев.

Эвристика - это не полностью математически обоснованный, но при этом практически полезный алгоритм. Особенности:

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

Алгоритм поиска $A^*$

Алгоритм поиска «А-звездочка» относится к эвристическим алгоритмам поиска по первому лучшему совпадению на графе с положительными ($>0$) весами рёбер, который находит маршрут с наименьшей стоимостью от одной вершины в другой.

В отличие от алгоритма Дейкстры, использует эвристическую функцию.

Идея алгоритма: $A^*$ пошагово просматривает все пути, ведущие от начальной вершины к конечной, пока не найдет минимальный путь. Как и все эвристические алгоритмы поиска, алгоритм сначала просматривает те маршруты и те ребра, которые кажутся ведущими к цели. От жадного алгоритма его отличает то, что при выборе вершины он учитывает весь путь до неё.

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

Затем $f(x) = h(x) + g(x)$ - к эвристической функции прибавляется путь до текущей вершины.

Структура Вирта - удобная структура для хранения планарных графов. Удобнее, чем списки смежности.

Псевдокод

FUNCTION A*(start,end)
	closedset = the empty set // Множество вершин, которые уже были обработаны(раскрыты)
	openset = {start} // Множество вершин(очередь), которые предстоит обработать(раскрыть).
					  // Изначально здесь присутствует только начальная вершина start.
	fromset = the empty set // Карта пройденных вершин. Используется функцией RECONSTRUCT_PATH
							для восстановления пути (вывода результата).
	
	// Заполняем свойства вершины start
	G(start) = COST(start,start) = 0 // Стоимость пути от начальной вершины. У start g(x) = 0.
	F(start) = G(start) + H(start,end) // h(x) - эвристическая оценка расстояния до цели.
	
	// Основной цикл алгоритма
	WHILE openset IS NOT EMPTY
		curr = MIN_F(openset) // Вершина из openset имеющая самую низкую оценку f(x).
		IF (curr = end) RETURN RECONSTRUCT_PATH(fromset,start,end) // Выводим результат.
		REMOVE curr FROM openset // Вершина curr пошла на обработку, а значит её следует удалить из очереди на обработку.
		ADD curr TO closedset // И добавить в список уже обработанных.
		
		FOREACH neighbour OF curr neighbours // Проверяем каждого соседа curr
			IF neighbour IN closedset CONTINUE // Пропускаем соседей из закрытого списка (предварительный, ожидаемый)
				tentative_g_score = G(curr) + COST(curr,neighbour) // Вычисляем g(x) для обрабатываемого соседа
			IF neighbour NOT IN openset // Если сосед curr ещё не в открытом списке
				ADD neighbour TO openset //добавим его туда
				tentative_is_better = TRUE // вводим признак того, что нужно обновить свойства для соседней вершины
			ELSE	// Сосед был в открытом списке, а значит мы уже знаем его g(x), h(x) и f(x)
				IF tentative_g_score < G(neighbour) // Вычисленная g(x) оказалась меньше, а значит нужно будет обновить значения g(x), h(x), f(x)
					tentative_is_better = TRUE
				ELSE // Вычисленная g(x) оказалась больше, чем имеющаяся в openset.
					 // Это означает, что из вершины curr путь через этого соседа дороже
					 // т.е. существует менее дорогой маршрут, пролегающий через этого соседа (из какой-то другой вершины, не из curr)
					 // Поэтому данного соседа мы игнорируем
					 tentative_is_better = FALSE
				 // Обновление свойств соседа.
				 IF tentative_is_better = TRUE
					fromset(neighbour) = curr //Вершина с которой мы пришли. Используется для реконструкции пути.
					G(neighbour) = tentative_g_score
					F(neighbour) = G(neighbour) + H(neighbour, end)
				// Обратите внимание, что если происходит обновление свойств - значит neighbour(сосед curr) так или иначе находится в openset.
				// Т.е. при следующей итерации внешнего цикла из openset будет извлечена вершина с наименьшей оценкой f(x).
				// Не исключено, что она окажется соседом нашего curr, которого мы только что добавили.
				// В общем это самая важная особенность алгоритма А*.
RETURN FAILURE // управление передаётся сюда когда openset пуст,а вершина end не найдена (путь найти не удалось)

// Восстанавливаем результироующий путь.
// Путь можно проследить только от заданной вершины(чаще всего это end) к старту(каждая вершина имеет пути находится в fromset, чем мы и воспользуемся).

FUNCTION RECONSTRUCT_PATH(fromset,start,end)
	pathset = the empty list // Упорядоченное множество результирующих вершин пути.
	curr = end // Поиск начинается от финиша.
	ADD curr TO pathset // Добавляем end в результирующий путь.
	
	WHILE curr <> start // Добавляем в путь все вершины от end до start.
		curr = fromset(curr) // Получаем вершину из которой пришли в curr.
		ADD curr TO pathset // Добавить вершину в результирующий путь.
RETURN REVERSE(pathset) // Так как мы построили путь от end к start, то результирующий набор вершин необходимо перевернуть.

Эвристическая функция

Доказано, что $A^*$ всегда дает лучший маршрут для конкретной эвристической функции.

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

Манхэттенское расстояние. При движении по сетке по четырем направлениям. $h(u) = |ux - goal.x| + |uy - goal.y|$
Расстояние Чебышева. При движении по 9 направлениям по сетке. $h(u) = \max ( |ux - goal.x|, |uy - goal.y| )$
Для планарного графа. $ h(u) = \sqrt{(ux - goal.x)^2 + (uy + goal.y)^2} $

Требования к эвристической функции:

Монотонность.
Согласование единиц измерения с неэвристической функцией. Если они измеряются в разных величинах (например, $g(x)$ — это расстояние в километрах, а $h(x)$ — оценка времени пути в часах) $А^*$ может выдать некорректный результат.

Свойства $A^*$

Допустимость. Если решение существует, с помощью этого алгоритма оно будет найдено.
Оптимальность. Найденное решение всегда оптимально.
Эффективность. Не существует в данный момент алгоритмов, который находят решение быстрее с применением той же эвристической функции. $A^*$ в ходе решения раскрывает минимальное количество вершин.

Временная сложность

Обычно алгоритм $А^*$ просматривает только часть вершин. Однако, в лабиринтах быстродействие приближается к худшему случае. Быстродействие алгоритма существенно зависит от двух факторов:

Точность эвристической функции.
Реализация контейнеров известных и исследованных вершин: наиболее затратными операциями в алгоритме есть операции сложения, изъятия и изменения элементов в списках известных и исследованных вершин. По их быстродействие существенно влияют конкретные реализации этих структур данных.

Пусть имеется множество вершин в графе, информация о вершинах и ребрах доступна до начала работы алгоритма, использованная эвристическая функция — монотонная. Список известных вершин реализован как бинарная куча, список исследованных — как массив. Тогда алгоритм $А^*$ имеет квадратичную зависимость от количества вершин графа и худшее время работы:

$$ O ( |V|^2 ) $$

Функция MIN_F(openset) может быть оптимизирована. Если каждая вершина хранится как указатель на соответствующий объект в куче, то время работы функции уменьшится с квадратичного до логарифмического, а общее время работы алгоритма — до линейно-логарифмического:

$$ O ( |V| \cdot \log |V| ) $$