Как работает эвристический алгоритм?

Подумайте об идеальной эвристике h(n). Он дает точное кратчайшее расстояние до цели из n.

Следовательно, функция стоимости f(s) для каждого узла s на кратчайшем пути будет одинаковой и равной длине кратчайшего пути: пройденное расстояние плюс точное кратчайшее расстояние до цели.

Так что нетрудно заметить, что для всех узлов кратчайшего пути s и любого заданного узла некратчайшего пути n мы имеем f(s) ‹ f(n).

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

Если у вас нет идеальной эвристики, алгоритм, очевидно, может совершать ошибки, потому что возможно f(n) ‹ f(s), поэтому алгоритм может «сойти с кратчайшего пути» по ненужной ветви.

Прелесть алгоритма в том, что до тех пор, пока эвристика допустима, он все равно найдет кратчайший путь, просто медленнее, чем идеальный.

Эвристика — это всего лишь хорошая обоснованная догадка. Аппроксимация гарантирует, что она находится в некоторых пределах. Алгоритм Кристофидеса является приближенным алгоритмом, но работает только с графом, удовлетворяющим неравенству треугольника (метрика tsp). Источник: https://cs.stackexchange.com/questions/10182/difference- алгоритм между эвристикой и аппроксимацией

Эвристическая функция действует как оценка наименьшей оставшейся стоимости завершения сквозного пути. f(n) = g(n) + h(n) ограничивает снизу наименьшую стоимость продления и завершения пути g(n). Таким образом, для допустимых эвристических функций гарантируется успех поиска.

Чем ближе эвристическая функция, тем быстрее поиск. Подумайте о крайнем случае, что h(n) = 0 вместо этого у вас будет поиск A, а если h(n) - это точно оставшаяся стоимость, что означает, что f(n) - это реальная стоимость, тогда поиск выполнен.